MIME-Version: 1.0 Server: CERN/3.0 Date: Sunday, 24-Nov-96 22:37:14 GMT Content-Type: text/html Content-Length: 3789 Last-Modified: Wednesday, 06-Nov-96 05:01:50 GMT
The exam will be comprehensive, covering all material we have covered in the course, including material tested on the two prelim exams. Roughly equal weight will be devoted to each of the three parts of the course.
I will ask you to do one formal proof, and it will probably be an undecidability proof. There may also be an essay question.
The primary source is the online lecture notes. Suggested supplementary readings are taken from the text by J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979; the appropriate sections are indicated beside each topic.
In addition to these specific topics, you will need to have a good general understanding of what it means for a set to be regular, context-free, recursive, and r.e.; of the capabilities of finite automata, pushdown automata, and Turing machines; and of how to describe sets using regular expressions and context-free grammars.
finite alphabets, strings, decision problems, Sigma*, operations on strings and sets 1.1-1.6 state transition systems, DFAs, delta^, regular sets 2.1-2.2 closure properties, the product construction, nondeterminism and NFAs, the subset construction, e-transitions 2.3-2.4, 3.2 patterns and regular expressions, converting regular expressions to finite automata and vice versa 2.5 Pumping Lemma for regular sets: formal statement, use of Pumping Lemma to show nonregularity 3.1 the quotient construction, DFA state minimization, Myhill-Nerode relations 3.4 two-way finite automata 2.6
CFGs and CFLs--definitions and examples 4.1-4.3 right- and left-linear grammars, Chomsky and Greibach normal forms 9.1, 4.5-4.6 PDAs--formal definition, examples, configurations, acceptance by empty stack and final state 5.1-5.2 converting NPDAs to CFGs and vice versa 5.3 Pumping Lemma for CFLs 6.1 Parsing Cocke-Kasami-Younger algorithm, closure properties of CFLs, DCFLs 6.2-6.3, 10
general computability, Turing machines, Church's Thesis, universality, configurations, r.e. and recursive sets 7.1-7.3, 7.6 Variants of the TM, nondeterminism, enumeration machines 7.4-7.5, 7.7-7.8 decidable and semidecidable problems, universal TMs, diagonalization, undecidability of halting and membership 8.1-8.3 decidable and undecidable problems, reductions 8.4 Rice's Theorem, VALCOMPS and undecidable problems for CFLs 8.4, 8.6 Other formalisms: type 0 grammars, Post systems, mu-recursive functions, while programs, lambda calculus, combinator logic Goedel's incompleteness theorem
CS381/481 home page