Exam 2 Topics - Fall 2019
-
Updates :
- : Final version
-
- The exam contains a few questions convering basic such as definitions, and the focus of the rest
is on designing grammars and machines and on applying algorithms.
- The exam will cover the following material:
Notes and Chapters 11, and 12
and an overview understanding of Pumping Theorems from Chapters 8 and 13
- Chapter 6: Regular Expressions: [RE will not be on the exam (ie postponed until the final)]
- Except that the exam occasionally uses a RE to describe a language, and so you should be able
to read a simple regular expression.
- Chapter 11: Context Free Grammars
- 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
- PDA M recognizes Language L
- Inherently Ambiguous Language [Not On Exam (NOE)]
- Chomsky Normal Form (CNF) [NOE]
- Symbols - Define the following grammar and PDA symbols and use them
appropriately:
- Single arrow (ie →)
- Double arrow - derives (ie ⇒)
- Double arrow starred (ie ⇒*)
- Yields in one step (⊦)
- Yields in zero or more step (⊦*)
- 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
- Give the RM and LM derivation of a string.
- Find the parse tree of a string that is in a grammar's language.
- 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]
- Chapter 13: Pushdown Automata (PDA)
- Basics: Definitions and Formalism
- 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 when a PDA accepts a string, rejects a string, or does neither.
- Define the language that a PDA accepts.
- Analysis and Synthesis:
- 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 natural PDA that recognizes the language of a given CFG,
- Determinism and Nondeterminism:
- Describe what it means for a PDA to be deterministic (ie no competing
transitions and no competition between accepting and making an empty
(ie ε/ε/x 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: Grammar to PDA and Finding a Parse
- Use the book's algorithm given to convert a grammar
into an equivalent PDA and explain the significance of this.
- Top Down : Basic algorithm (expand and match), tree creation, relation between parse and derivation
- Bottom Up (shift and reduce): Same topics as TD
- LL and LR grammars: connection to deterministic TD/BU parsing, importance of LR category
- General: 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 < 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).
- Chapters 8 and 13: Pumping Lemmas
- Explain what a Pumping Theorem/Lemma (PL) is used to prove
(in the context of both Regular and CF PL).
- Explain why long strings are pumpable (both regular and CF).
- Postponed until the final: Regular expressions:
- Basics:
- 8 forms: 3 base case, 5 recursive, 2 shorthands, parens
- L(α) - language described or defined by RE α
- Common operations and idioms
- Precedence
- Be able to analyze a RE
- Be able to create a RE to generate a specified language
- Kleene's Theorem
- RE to NDFSM
-
ndfsm to re: standard form and ripping states