Exam 2 Topics - Fall 2015
- 2015 Nov 17 03:43:03 PM: Final version
- 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
- Definitions: Define the following terms and/or
and use them appropriately
- Context Free Grammar (CFG)
- Language of a grammar
- Context Free Language (CFL)
- Derive in 0 or more steps
- Derive Ambiguously
- Ambiguous Grammar
- Inherently Ambiguous Language
- Chomsky Normal Form (CNF) [NOE]
- PDA M recognizes Language L
- Grammar and PDA Symbols - Define the following symbols and use them
- Single arrow (ie →)
- Double arrow (ie ⇒)
- Double arrow starred
- Yields (with and without star)
- 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]
Pushdown Automata (PDA)
- Describe when PDA accepts and rejects a string and accepts a language.
- Describe the difference in components and operation between a PDA, a DFSM, and/or a NDFSM
- Describe the parts in the formal definition of a PDA and a
configuration and computation
- Convert between the formal and graphical representations of a given PDA
- Identify the correspondences between the formal and graphical representations of a given PDA
- Describe the basic operation of a PDA, including how a PDA recognizes a string
- Trace the behavior of a given PDA on a given input string
- Analyze a PDA to identify the language it recognizes
- Create a PDA that recognizes a given language
- Create a PDA that recognizes the language of a given CFG, either natural or using the CFG to PDA algorithm.
- Describe what it means for a PDA to be deterministic (ie no competing
transitions and no competition between accepting and making an empty
- 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.
- 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
Context Free Languages
- State and explain the following listing of the language
recognition/generation power of various machines:
DFSM = NFSM < DPDA < NDPDA = CFG
- 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
- Use the algorithm given to convert a grammar
into an equivalent PDA and explain the significance of this.
- Explain what a Pumping Lemma is used to prove.
- Explain why long strings are pumpable.
- [NOE] State the Pumping Theorem for Regular Languages
- [NOE] Use a Pumping Lemma to prove an intuitive proof that a simple language is not Regular.