CSE 322 Introduction to Formal Models in Computer Science

Final exam preparation

Remember that the final exam is Monday, December 14 at 12:30-2:20 in our regular classroom. There will be a review session Sunday, December 13 at 3:00 pm, in our regular classroom. (You will need to bring your card-key to get in since the building is closed.) Please bring your questions.

The final exam will cover the entire course but particularly the following topics. There will be some emphasis on the material not covered on the first midterm.

  1. Strings and languages and operations on them.

  2. Regular expressions and regular languages.

  3. Deterministic finite automata: Formal definition as well as state diagrams.

  4. Nondeterministic finite automata: Formal definition as well as state diagrams.

  5. Converting NFAs to DFAs: The Subset construction

  6. DFAs for string matching.

  7. Every regular language is accepted by some finite automaton.

  8. Kleene's Theorem: Construction of regular expressions from NFAs.

  9. Closure of regular languages under intersection and complement, as well as union, concatenation and Kleene star.

  10. The Pumping Lemma for Regular Languages; Using it to prove languages non-regular

  11. Myhill-Nerode theorem and its implications: Using it to prove that languages are not regular. The fact that there is a unique minimal DFA for any regular language.

  12. Minimization algorithm for DFA's.

  13. Context-free grammars and languages: Formal definitions, derivations and parse trees, ambiguity.

  14. Pushdown Automata: Formal definitions and acceptance.

  15. Every CFL is accepted by some PDA: Top-down and bottom-up constructions of PDA from CFG.

  16. The fact that languages accepted by PDAs are CFLs.

  17. Closure properties of CFL's: Union, concatenation, Kleene star, intersection with regular sets.

  18. Pumping Lemma for CFL's: Proofs that languages are not CFL's, CFL's not closed under intersection or complement.

  19. Recognizing whether languages are regular, context-free or neither.

  20. Chomsky Normal Form and the fact that every CFG can be converted to Chomsky Normal Form.

  21. The fact that membership in any CFL can be recognized in O(n3) time (by the Cocke-Kasami-Younger algorithm).

  22. Diagonalization and countability.

  23. The fact that certain natural properties of programs, such as the halting problem, are not decidable by any program.