Final Exam - Main items

• Set Theory (Ch. 1)

• Regular Languages (Ch. 2-4)
  • DFA, NFA, Reg. Grammar, Reg. Expr
  • Conversions such as NFA -> DFA -> min DFA
  • closure properties
  • Pumping lemma

• Context-free Grammars (Ch. 5)
  • write a CFG
  • ambiguous grammar
  • brute force parsing

• LL and LR Parsing (handout, JFLAP book)
  • comparison to brute force parser
  • how do they relate to NPDA
  • first and follow sets
  • build LL(k) parse table
  • build LR(1) parse table
  • understand whether or not a language is LL(3), LR(1)

• Transforming grammars (Ch. 6)
  • transformations: substitution, CNF, remove lamda, unit and useless
  • recognize grammar forms
  • given algorithms for transformations as they appear on handout

• NPDA (Ch. 7)
  • formally define a PDA
  • write an NPDA
  • theorems - know general idea
  • CFG -> NPDA
  • NPDA -> CFG
  • NPDA vs DPDA

• Properties of CFL (Ch. 8)
  • CFL pumping lemma given
  • apply pumping lemma
  • theorems - know general idea

• L-systems
  • Definition of L-system
  • write or draw an L-system
  • comparison of L-system grammar to chomsky grammar

• Turing Machines (Ch. 9)
  • formally define a TM
  • language acceptor vs transducer
  • write a TM
  • running time

• Turing Machines Building Blocks (handout)
  • write a TM with building block notation
  • running time

• Other Models of TM (Chap. 10)
  • variations of TM and proof of equivalence
  • nondeterministic TM
  • Universal TM
  • Linear Bounded Automata

• CYK Parsing (Ch. 6.3)
  • Dynamic programming algorithm
  • cubic time worst case
  • build CYK parse table

• Hierarchy of Formal Languages and Automata (Chap 11)
  • recursive vs rec. enum. languages
  • How do all the languages we've studied relate?
  • unrestricted grammar, parse tree
  • context-sensitive grammars and languages

• Decidability (Chap. 12.1)
  • What is the halting problem?

• Compilers (Handout)
  • How are automata theory and languages used to design and write compilers?
  • What did you do in Projects 1, 2, and 3?

Ways to Study for the Exam

• Old tests (see link in index)
• homework problems
• problems in the book
• use JFLAP to check problems

---

Final Exam Logistics

• Closed book, closed notes, closed neighbor
• About a 2 hour exam, you have 3 hours to complete it.
• Exam is Saturday 2pm, May 3, in LSRC D106

---

Susan H. Rodger