Exam 2 Topics  Fall 2015

Updates :
 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
expressions
and use them appropriately
 Context Free Grammar (CFG)
 Language of a grammar
 Context Free Language (CFL)
 Derivation
 Derive
 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
appropriately:
 Single arrow (ie →)
 Double arrow (ie ⇒)
 Double arrow starred
 Yields (with and without star)
 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]
 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
transition)
 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.
 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
 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.
 Pumping Lemma
 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.