CSE 322 Introduction to Formal Models in Computer Science

Final exam preparation

Remember that the final exam is Tuesday, June 6 at 2:30-4:20 in our regular classroom. There will be a review session Monday, June 5 at ??? at a location to be announced. Please bring your questions.

The final exam will cover the entire course but particularly the following topics. There will be some emphasis on the CFL material.

  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 NFA's to DFA's: The Subset construction

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

  7. Kleene's Theorem: Every language accepted by a finite automaton is regular.

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

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

  10. 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.

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

  12. Pushdown Automata: Formal definitions and acceptance

  13. Every CFL is accepted by some PDA: Construction of PDA from CFG.

  14. The fact that everything accepted by a PDA is a CFL.

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

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

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

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

  19. Diagonalization and countability.

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