Final Exam Study Guide
CSE 322: Introduction to Formal Models in Computer Science
Winter 2003

Final Exam, March 18, 2003, 8:30 - 10:20

• Midterm Policies
  • The final exam is open book and open notes. Open notes includes homeworks and their solutions. No other materials are allowed.
  • The exam begins promptly at 8:30 and ends at 10:20.
• Topics covered
  • Alphabets, strings, and languages. Operations of concatenation and reversal on strings. Operations of union, complement, intersection, concatenation, powering, Kleene star, and reversal on languages.
  • Finite automata. The equivalence of deterministic and nondeterministic finite automata. The subset construction. The cross product construction. Behavioral lemmas and their use. Finding lower bounds on the number of states for certain regular languages. Running NFAs deterministically by maintaining a set of states.
  • Regular expressions. Regular languages and ways to prove properties about regular languages using induction on regular expression length.
  • Finite automata and regular expressions. Equivalence of finite automata and regular expressions. Finite automata constructions for union, concatenation, Kleene star, complement, and intersection and other operations.
  • Nonregular languages. Direct proofs of nonregular languages using the pigeon hole principle. The pumping lemma for regular languages and its applications.
  • Algorithms for finite state automata. Algorithm for removing e-moves. State elimination algorithm for going from an NFA to a regular expression. Polynomial time algorithm for testing membership for NFAs without constructing the equivalent DFA. Algorithms for testing emptiness and finiteness of languages accepted by finite automata. State minimization for DFAs.
  • Context-free grammars. Ambiguity and Chomsky normal form. Closure properties: union, concatenation, Kleene star, intersection with a regular language, reversal, prefix. Not closed under complement and intersection.
  • Pushdown automata. Equivalence with context-free grammars. Top-down and bottom-up constructions of PDAs from grammars. Deterministic PDAs.
  • Non-context-free languages. The pumping lemma and applications.
  • Algorithms for context-free grammars. Emptiness, finiteness, and membership (membership was not studied in detail).
  • Undecidable problems about context-free grammars. Ambiguity, non-empty intersection, everything, equivalence. (No proofs)
  • Undecidability of the halting problem for Java programs.
  • Turing machines. Equivalence of multitape and single tape Turing machines. Church-Turing thesis. The universal Turing machine. Distinction between decidable and recursively enumerable.
  • Context-free grammars for data compression. Sequitur.
  • Cellular automata. "A new kind of science." The game of life.s
• Study suggestions
  • Do the old final exam in an exam setting.
  • Work in study groups to help each other out in preparation. Give each other problems to do in an exam setting. After doing the problems alone, critique each others answers.
  • Practice each algorithm to improve understanding and accuracy. Creating an equivalent DFA from a NFA. Creating an equivalent regular expression from a NFA. Creating an equivalent NFA from a regular expression. Removing epsilon-transitions. Chomsky normal form. Top down and bottom up constructions of PDAs from context-free grammars.
  • Review chapters 1, 2, 3.1, 3.2, 4, 5.1, 5.2, 5.4, 6, 7, 8.1, 8.2, 8.3, 8.4, 8.6
  • Do concrete problems from the book.
    
  • A number of topics are not covered in the book that you should review. Bottom up construction of PDA from a context-free grammar. Sequitur. Cellular automata. The Universal Turing Machine has some similarity to what is found in section 8.6.