Chapter 7 --- Little Quiz                                                        

1. Which is incorrect? (a) CFG’s may be transformed into Chomsky normal form.(b) All properties of RL’s are also possessed by the CFL’s.(c) There are many undecidable problems about CFL’s.(d) CFG’s may be simplified into Greiback normal form.

2. Which of the following need not be removed to form Chomsky-normal-form grammars?(a) Useless symbols.(b) e-productions.(c) Unit productions.(d) Accessible symbols.

3. Which of the following is correct?(a) The pumping lemma can be used to prove that a language is a CFL.(b) L = {ww | w is a string of 0's and 1's} is a CFL.(c) L = {ww^R | w is a string of 0's and 1's} is a CFL.(d) L = {wcw^R | w is a string of 0's and 1's} is an RL

4. Which of the following is correct?(a) CFL’s are closed under intersection.(b) CFL’s are closed under difference.(c) CFL’s are closed under substitution.(d) CFL’s are closed under complementation.

5. Which of the following problems is decidable?(a) Is the intersection of two CFL’s empty?(b) Whether a given string is in a CFL?(c) Is a given CFG G ambiguous?(d) Are two CFL’s the same?