Exam 2 Study Guide
The second exam will cover context-free languages. Some questions you may be asked to solve on the exam are:
- Draw PDA's for a given language or to solve problems about PDA's. Study examples shown on pages 115 and 116. Try to generate PDA's for Problems 2.22 through 2.24.
- Create grammars to recognize certain languages. In particular, see example 2.4 on Page 105. Also, see Problem 2.27.
- Create multiple parse trees for ambiguous grammars. Study Problem 2.46 (just show the part that it is ambiguous).
- Show a language is not context-free with the pumping lemma. See Problems 2.31 through 2.33.
- Consider possible variations of the standard single-stack, nondeterministic PDA.
- Recall when we proved that the class of regular languages is closed under union, concatenation, and star (see pages 59-63). Can you show that the class of CFL's is closed under certain operators? Study Problem 2.25 on page 157.
Additional practice:
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc
Show that this grammar is ambiguous by drawing more than one parse tree. Can you draw three different parse trees? Then, draw an equivalent PDA.
- Modify the following PDA so that it recognizes the language {0n1n} ∪ {0n10n}.
