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 CS381/481 Fall 96 Study Guide

CS381/481 Fall 1996
Automata and Computability Theory
Final Exam Study Guide


The final exam will be 2.5 hours, open book and notes. All questions are roughly equal weight.

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 Automata and Regular Expressions

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   

Pushdown Automata and Context-Free Languages

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   

Turing Machines and General Computability

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