TAFL Quiz-3 (Module-2)

Let G be a CFG in Chomsky Normal form (CNF). In order To derive a string of terminals of length n , the number of productions to be used is:

• 2n + 1

• 2n - 1

• 2n

• None of these

Recursively enumerable languages are not closed under:

• Complementation

• Union

• Intersection

• none of these

Which of the following statement is wrong?

• Every recursive language is recursively enumerable.

• A language is accepted by FA if and only if it is context free.

• Recursive languages are closed under intersection

• A language is accepted by FA if and only if it is right linear.

Which of the following is true?

• The complement of a recursive language is recursive.

• The complement of a recursively enumerable language is recursively enumerable.

• The complement of a recursive language is either recursive or recursively enumerable.

• The complement of a context-free language is context-free.

If there exists a language L, for which there exists a TM, T,

that accepts every word in L and either rejects or loops for every word that is not in L, is called:

• Recursive

• Recursively enumerable

• NP-HARD

• None of these

Universal TM influenced the concept of:

• interpretative implementation of programming language.

• stored program computers.

• computability.

• all of these.

Which of the following statements is/are true?

I. Recursive languages are closed under complementation.

II. Recursively enumerable languages are closed under union.

III. Recursively enumerable languages are closed under complementation.

• I only

• II only

• I and II

• None of these

Type 0 Grammar is accepted by:

• PDA

• DFA

• LBA

• Turing Machine

Which one of the following string(s) is accepted by the above TM?

• aabbb

• aabbaaaa

• abbb

• ab

How many derivation trees will be possible for the string w = aabbab for the following CFG.

S ⟶ aB | bA

A ⟶ a | aS | bAA

B ⟶ b | bS | aBB

• 2

• 3

• 4

• 5