Final Exam Study Guide
CSE 322: Introduction to Formal Models in Computer Science
Autumn 1998

Final Exam, Friday, December 11, 1998, 8:30 - 10:20 am

• Final Exam Policies
  • The final is closed book.
  • An 8 1/2 X 11 inch blue (or green) book is required.
  • You may put your own hand written notes in your blue book to aid you during the exam.
  • The exam begins promptly at 8:30 am and ends at 10:20 am.
• 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.
  • Regular expressions. Regular languages and ways to prove properties about regular languages using induction on regular expression length.
  • Finite automata. the equivalence of deterministic and nondeterministic finite automata. The subset construction.
  • Finite automata and regular expressions. Equivalence of finite automata and regular expressions. Finite automata constructions for union, concatenation, Kleene star, complement, and intersection. The cross product construction.
  • Nonregular languages. Direct proofs of nonregular languages using the pigeon hole principle. The pumping lemma for regular languages and its applications. Finding lower bounds on the number of states for certain regular languages.
  • Algorithms for finite state automata. Algorithm for removing e-moves. Polynomial time algorithm for testing membership for NFAs. Algorithms for testing emptiness and finiteness of languages accepted by finite automata. Boolean matrices to represent graphs and their use in algorithms for finite state automata. Warshall's algorithm.
  • Context-free grammars. Derivations, leftmost derivations, and parse trees. Ambibuous grammars. Regular languages are also context-free.
  • Pushdown automata. Equivalence of context-free grammars and pushdown automata. Top-down and bottom-up constructions of pushdown automata from context-free grammars. Deterministic pushdown automata. Languages that are context-free but not deterministic context free.
  • Pumping lemma and closure properties. The stronger pumping lemma. Closure under union, concatenation, Kleene star, and intersection with a regular language. Techniques to show that languages are not context-free.
  • Algorithms about context-free grammars. Grammar manipulation algorithms such as shortening the righthand side of productions and eliminating e-productions. Closure algorithms for testing properties like emptiness.
  • Turing machines. Designing simple Turing machines using diagrams. Recursive and recursively enumerable languages. Simulating multiple tapes and random access memory.
  • Undecidablilty. The universal Turing machine. Undecidability of the halting problem. Other undecidable problems including those for context-free grammars.
• Study suggestions
  • Do the old final exam.
  • Work in study groups to help each other out in preparation
  • Review chapter 1, all sections, chapter 2, all sections except section 2.5, chapter 3, all sections, chapter 4, sections 1 to 4, and chapter 5 sections 1 to 5.
  • Do concrete problems from the book:

    1.7- 1.7.4, 1.7.5, 1.7.6	1.8- 1.8.1, 1.8.2, 1.8.3, 1.8.5	2.1- 2.1.1, 2.1.3
    2.2- 2.2.1, 2.2.3, 2.2.9	2.3- 2.3.4, 2.3.7	2.4- 2.4.5, 2.4.8
    2.6- 2.6.2	3.1- 3.1.1, 3.1.2, 3.1,3, 3.1.4	3.2- 3.2.2, 3.2.3, 3.2.4
    3.3- 3.3.1, 3.3.2	3.5- 3.5.5, 3.5.5, 3.5.14	3.7- 3.7.1, 3.7.10
    4.1- 4.1.1, 4.1.2, 4.1.8	4.2- 4.2.1	5.2- 5.2.2
    5.4- 5.4.1, 5.4.2

  • Practice with the techniques we used in class but are not found in the book: showing lower bounds on the number of states needed to accept certain regular languages, using Boolean matrices as an aid in solving problems about finite automata, and using the stronger pumping lemma to show languages are not context-free.