# Exam 2 Topics - Fall 2017

1. No updates at this time.

1. The exam will focus on the following material: Notes and Chapters 11, 12, 16 (skip 14 and 15) and an overview understanding of Pumping Theorems from Chapters 8 and 13

2. Definitions: Define the following terms and/or expressions and use them appropriately
1. Context Free Grammar (CFG)
2. Language of a grammar
3. Context Free Language (CFL)
4. Derivation
5. Derive
6. Derive in 0 or more steps
7. Derive Ambiguously
8. Ambiguous Grammar
9. Inherently Ambiguous Language
10. Chomsky Normal Form (CNF) [Not On Exam (NOE)]
11. PDA M recognizes Language L

3. Grammar and PDA Symbols - Define the following symbols and use them appropriately:
• Single arrow (ie →)
• Double arrow - derives (ie ⇒)
• Double arrow starred (ie ⇒*)
• Yields (⊦ and ⊦*)

4. Grammars
• Describe the parts in the formal definition of a CFG
• Identify the parts of a given grammar
• Create a grammar that generates a given language
• Analyze a given grammar to find the language it generates
• Find the derivation of a given string with a given grammar, if one exists
• Define rightmost and leftmost derivations, and give the RM and LM derivation of a string.
• Find the parse tree of a given string with a given grammar, if one exists
• Identify the correspondences among a grammar, derivation of a string, and the parse tree for that string
• Prove that a given grammar is ambiguous
• Recognize whether a grammar is in CNF [NOE]

5. Pushdown Automata (PDA)
1. Describe when a PDA accepts a string, rejects a string, or does neither.
2. Define the language that a PDA accepts.
3. Describe the difference in components and operation between a PDA, a DFSM, and/or a NDFSM
4. Describe the parts in the formal definition of a PDA and a configuration and computation

5. Convert between the formal and graphical representations of a given PDA
6. Identify the correspondences between the formal and graphical representations of a given PDA

7. Describe the basic operation of a PDA, including how a PDA recognizes a string
8. Trace the behavior of a given PDA on a given input string

9. Analyze a PDA to identify the language it recognizes
10. Create a PDA that recognizes a given language

11. Create a PDA that recognizes the language of a given CFG, either natural or using the CFG to PDA algorithm.

12. Describe what it means for a PDA to be deterministic (ie no competing transitions and no competition between accepting and making an empty transition)

13. Describe 2 ways to reduce nondeterminism in a machine (eg push stack marker and mark end of input), and create a deterministic PDA that uses these techniques.

6. Parsing
• Top Down : Basic algorithm, tree creation, relation between parse and derivation
• Bottom Up
• LL and LR grammars: connection to deterministic TD/BU parsing, importance of LR category

7. Context Free Languages
1. State and explain the following listing of the language recognition/generation power of various machines:
DFSM = NFSM < DPDA < NDPDA = CFG

2. State and explain the following listing of languages, and give examples of languages in each category:
Regular Languages < Deterministic Context Free Languages < Context Free Languages < Non-CFL
• For each category above, give an example language that is in the category and not in the next larger category (if there is a larger category).

3. Use the algorithm given to convert a grammar into an equivalent PDA and explain the significance of this.

8. Pumping Lemma
1. Explain what a Pumping Theorem/Lemma (PL) is used to prove (in the context of both Regular and CF PL).
2. Explain why long strings are pumpable (both regular and CF).
3. [NOE] State the Pumping Theorem for Regular Languages
4. [NOE] Use a Pumping Lemma to prove an intuitive proof that a simple language is not Regular/CF.