Computer Science 394

Automata Theory

Fall 1996

Syllabus

Instructor:

Brian L. Stuart

Office:

Math 419

Office Phone:

726-3725

Office Hours:

8:00-9:00 Monday through Friday, 1:00-3:00 Tuesday and Wednesday You may be sure of catching me in at those times, but you are free to drop in anytime to discuss the class (or anything else for that matter).

Text:

The Language of Machines by Floyd, Robert W. and Beigel, Richard.

Objectives:

In this class, we will study the Chomsky heirarchy of languages and the computational models to which they correspond. Our focus will be on the theoretical foundations of these languages and machines. We will prove a number of characteristics of the heirarchy and of various models within each level. While it won't be our main focus, we will catch a glimpse into how these concepts can be applied to real problems and there will be a few programming assignments to that effect.

Planned List of Topics:

Below is a list of topics to be covered during this course. Section and exercize numbers refer to the course text.

• Introduction, Chomsky's heirarchy, Strings, Languages
• Programs, devices and machines; Sec. 1.1-8; Ex. 1.1-1,3,5 1.2-2, 1.3-3,6,8 1.4-1,2 1.5-1 1.7-3
• Non-Determinism; Sec. 1.9; Ex. 1.9-1,3,4,5,9 1.10-4
• Devices, Machines, Instructions, Initiators and Terminators, Programs; Sec. 2.1-6; Ex. 2.1-1 2.2-2,3 2.4-1,2 2.6-1,2,3,7,8,12
• Traces Blocking, Acceptors, Recognizers, Transducers; Sec. 2.7-9; Ex. 2.7-1(p 136) 2.7-2,3,4(p 139) 2.8-2 2.9-1,2,6,7 2.10-4
• Simulation, Commutative Diagrams, Lockstep Simulation; Sec. 3.1-2; Ex. 3.2-1,2,3,4
• Subprogram Simulation; Sec. 3.3-4; Ex. 3.3-1,2,3,6,7,9 3.3-10 3.4-1,3,6,7,8,12,15,16,18 3.5-1,2
• Regular Expressions and Languages; Sec. 4.1-3; Ex. 4.1-1,2,3 4.2-1,2,3,4 4.3-1,4
• Kleene's Theorem; Sec. 4.4; Ex. 4.4-1,2,3,4,6,7,9
• From Regular Expression to Non-Deterministic Finite Acceptor; Sec. 4.5; Ex. 4.5-1,2,3
• From NFA to DFA; Sec. 4.6; Ex. 4.6-1,3,4,5,8
• Minimal DFRs; Sec. 4.7; Ex. 4.7-3,4,5,6,11,16,19,20,22
• Closure Properties of Regular Languages; Sec. 4.8; Ex. 4.8-1,2,4,6,10,11
• Pumping Lemmas for Regular Languages; Sec. 4.9; Ex. 4.9-1,5,6 4.10-1,3,5,7
• Context Free Grammars and Languages; Sec. 5.1,3,5; Ex. 5.1-1,2 5.3-1,2,3,4
• Context Free Grammars are Equivalent to Non-Deterministic Stack Acceptors; Sec. 5.6; Ex. 5.6-1,2,3
• Pumping Lemmas for Contex Free Languages; Sec. 5.8; Ex. 5.8-1,3,4,7
• Ambiguity in Contex Free Languages; Sec. 5.9; Ex. 5.9-1,2,3,4 5.13-2
• Closure Properties of Context Free Languages; Sec. 6.1; Ex. 6.1-2,3,5,7
• DSA is equivalent to DSR, but NSA is not equivalent to DSA; Sec. 6.2-4; Ex. 6.4-2,3,4,6
• Two Counters are equivalent to a Stack; Sec. 6.5-6; Ex. 6.5-1,2,3 6.6-1 6.8-1,2
• Turing Machines, Two Stacks are Equivalent to a Tape; Sec. 7.1-2; Ex. 7.1-1,2,3,6(p 450) 7.2-1,2,4
• Random Access Machines and Universal Turing Machines; Sec. 7.3-4; Ex. 7.4-1
• Recursive and Recursively Enumerable Problems; Sec. 7.6; Ex. 7.6-1,3,4,5,6,7,10
• The Halting Problem and other Undecidable Problems; Sec. 7.7; Ex. 7.7-1 7.15-4
• Reductions; Sec. 7.9; Ex. 7.9-1,2,3
• Rice's Theorem; Sec 8.1; Ex. 8.1-2,3
• Oracles and Turning Reductions; Sec. 8.4; Ex. 8.4-1,2,3,4(p 577) 8.4-5(p 580)
• The Problem Classes P and NP; Sec. 9.1; Ex. 9.1-1,3,4,5,8
• NP-Completeness; Sec. 9.2-4; Ex. 9.2-1,2,3,4,5 9.3-5 9.4-1,2

Grading:

There will be approximately 3 programming assignment three exams and a few theoretical assignments. The exact breakdown is as follows:

First Mid-Term Exam   13%
Second Mid-Term Exam  13%
Final Exam            20%
Program 1             13%
Program 2             13%
Program 3             13%
Misc. Assignments     15%

All work will be conducted according to Rhodes' Honor Code.