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 such as GNF
  • 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
  • Write algorithm for multi-tape TM
  • Universal TM
  • Linear Bounded Automata

• 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

• Understand your Exam 1-3
• 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 Monday 7pm, April 25

COURSE EVALUATION

Fill out the Course evaluation! As of 4/19 we have 45% have filled it out

• If we get 65%, will give everyone 1 extra point on final exam
• If we get 75%, will give everyone an additional extra point on final exam

---

Susan H. Rodger