http:^^www.cs.cornell.edu^info^courses^current^cs481^studyguide.html

来自「This data set contains WWW-pages collect」· HTML 代码 · 共 130 行

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

<title>CS381/481 Fall 96 Study Guide</title>

<h1>
CS381/481 Fall 1996<br>
Automata and Computability Theory<br>
Final Exam Study Guide
</h1>

<hr>

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

<p> 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.

<p> I will ask you to do one formal proof, and it will probably be an
undecidability proof.  There may also be an essay question.

<p> The primary source is the online lecture notes.  Suggested
supplementary readings are taken from the text by J. E. Hopcroft and
J. D. Ullman, <i>Introduction to Automata Theory, Languages, and
Computation</i>, Addison-Wesley, 1979; the appropriate sections are
indicated beside each topic.

<p> 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.

<hr>

<h3>Finite Automata and Regular Expressions</h3>

<pre>
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   
</pre>

<h3>Pushdown Automata and Context-Free Languages</h3>

<pre>
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   
</pre>

<h3>Turing Machines and General Computability</h3>

<pre>
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             
<pre>

<hr>
<!WA0><!WA0><!WA0><!WA0><img align=top src="http://www.cs.cornell.edu/Info/Misc/images/hand_point1.gif">
<!WA1><!WA1><!WA1><!WA1><a href="http://www.cs.cornell.edu/Info/Courses/Current/CS481/CS481.html">CS381/481 home page</a>