Topic Outline

Examination II

- Regular Languages
- Define
- Pumping Lemma
- Prove a language is not regular
- Context Free Grammers
- Definition
- Give grammer for a language
- Give a parse tree
- Give a derivation
- Ambigous grammers
- Convert regular expressions to grammers
- Pushdown Automata
- Definition
- Parse a string
- Treat CFG as a Pushdown atuomata
- Relationship between PDA and CFLs.
- Pumping Lemma for CFG
- State
- State contrapositive
- Prove a language is not context free
- Show a language is not regular but is context free.
- Other items from the first examination.