TOC 4B

Which transformation step is needed to convert a CFG to CNF?

• Remove left recursion

• Remove ε-productions

• Remove unit productions

• All of the above

Which of the following is not a step in converting CFG to GNF?

• Left recursion removal

• ε-production removal

• Rewriting RHS to start with terminal

• Push symbols to stack

CNF guarantees that every production has:

• One terminal

• Two variables or one terminal

• Unit production

• At least one ε

In GNF, the RHS always begins with:

• Terminal

• Variable

• ε

• Combination

Which language violates the CFL pumping lemma?

• {aⁿbⁿcⁿ | n ≥ 1}

• {aⁿbⁿ | n ≥ 1}

• Palindromes

• {aⁿbᵐ | n ≠ m}

Pumping lemma for CFLs states the string can be broken as:

• uvxy

• uvxyz

• uvx

• uvxyz where |vxy| ≤ p and |vy| ≥ 1

CFLs are not closed under which operation:

• Complement

• Union

• Substitution

• Reversal

Which of the following is closed for CFLs:

• Intersection with regular languages

• Intersection with CFLs

• Complement

• None

A TM with two tapes is:

• More powerful than single tape

• Equivalent to single tape

• Weaker than single tape

• Accepts less languages

Turing-recognizable languages are also called:

• Recursive

• Recursively enumerable

• Context-sensitive

• Regular