## CSE 322
Introduction to Formal Models in Computer Science

## Final exam preparation

Remember that the final exam is Monday, March 15 at 2:30-4:20 in our regular
classroom.
There will be a review session Sunday, March 14 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.

- Strings and languages and operations on them.
- Regular expressions and regular languages.
- Deterministic finite automata: Formal definition
as well as state diagrams.
- Nondeterministic finite automata: Formal definition
as well as state diagrams.
- Converting NFAs to DFAs: The Subset construction
- DFAs for string matching.
- Every regular language is accepted by some finite automaton.
- Kleene's Theorem: Construction of regular expressions from NFAs.
- Closure of regular languages under intersection and complement, as
well as union, concatenation and Kleene star.
- The Pumping Lemma for Regular Languages; Using it to prove languages
non-regular
- 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.
- Minimization algorithm for DFA's.
- Context-free grammars and languages: Formal definitions,
derivations and parse trees, ambiguity.
- Pushdown Automata: Formal definitions and acceptance.
- Every CFL is accepted by some PDA: Top-down and bottom-up constructions
of PDA from CFG.
- The fact that languages accepted by PDAs are CFLs.
- Closure properties of CFL's: Union, concatenation, Kleene star,
intersection with regular sets.
- Pumping Lemma for CFL's: Proofs that languages are not CFL's,
CFL's not closed under intersection or complement.
- Recognizing whether languages are regular, context-free or neither.
- The fact that membership in any CFL can be recognized in O(n
^{3}) time
(by the Cocke-Kasami-Younger algorithm).
- Diagonalization and countability.
- The fact that certain natural properties of programs, such as the
halting problem, are not decidable by any program.