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

Midterm Exam, October 31, 2003

• Midterm Policies
  • The midterm allows for open book and open notes. Bring the text book and your own personal notes. Nothing else.
  • The exam begins promptly at 1:30 and ends at 2: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.
  • 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. State elimination algorithm for finding a regular expression equivalent to a NFA.
  • 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. Polynomial time algorithm for testing membership for NFAs without constructing the equivalent DFA (running an NFA deterministically). Algorithms for testing emptiness and finiteness of languages accepted by finite automata. Expressing a problem about finite automata as a problem about graphs. Warshall's algorithms for computing the reflexive, transitive closure of a graph.
• Study suggestions
  • Do the old midterm 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.
  • Review chapters 0 and 1.
  • Do concrete problems from the book:
    1.12, 1.14, 1.16, 1.17, 1.18, 1.23, 1.31, 1.32, 1.37.