TOC 4A

What is Chomsky Normal Form (CNF)?

• Every production is of form A → aB

• A → BC or A → a

• A → a or ε

• A → aB or ε

Which of the following is not allowed in CNF?

• A → a

• A → BC

• A → ε (except S → ε)

• A → B

In Greibach Normal Form (GNF), productions are of the form:

• A → a

• A → aB

• A → aα (a terminal followed by variables)

• A → αa

Which normal form removes left recursion?

• CNF

• GNF

• None

• Both

Which of these can simplify a CFG?

• Removing useless symbols

• Removing ε-productions

• Removing unit productions

• All of the above

The pumping lemma for CFLs is used to:

• Prove regularity

• Prove a language is context-free

• Prove a language is not context-free

• Generate languages

Pumping lemma applies to:

• Regular languages only

• All context-free languages

• Recursive languages

• All grammars

Which is a closure property of CFLs?

• Union

• Concatenation

• Kleene star

• All of the above

CFLs are not closed under:

• Union

• Intersection

• Reversal

• Concatenation

Which operation is CFL not closed under?

• Complement

• Union

• Star

• Concatenation