COSC 460(2)

COSC 460 Theory of Computation

Prerequisite: COSC 310 or instructor permission

Formal methods for describing and analyzing programming languages and algorithms. Backus-Naur forms; productions; regular expressions; introduction to automata theory; Turing machines; recent concepts in algorithm theory computability.

Course Outcomes

Upon successful completion of this course, the student should be able to:

• Define languages by abstract, recursive definitions and by regular expressions.
• Design a finite automaton to recognize a given regular language.
• Transform a language into regular expression or finite automaton or transition graph.
• Define deterministic and nondeterministic finite automata.
• Prove properties of regular languages and classify them.
• Determine decidability, finiteness and equivalence properties.
• Define relationship between regular languages and context-free grammars.
• Building a context-free grammar for pushdown automata.
• Determine whether a given language is context-free language or not.
• Prove properties of context-free languages.
• Design Turing machine and Post machine for a given language.
• Discuss the concept of computability.

Detailed Course Outline
Part I:  Automata Theory
A. Languages — 3 hours
a. Languages in  the abstract
b. Kleene closure
c. Recursive definition
d. Arithmetic expression—language
e. Defining languages by regular expression
f. Languages associated with regular expression
g. Finite languages
B. Finite Automata — 2 hours
a. Defining  languages by Finite Automata
b. Finite Automata and their languages
c. EVEN-EVEN languages
C. Transition Graph — 4 hours
a. Defining transition graphs
b. Generalized transition graphs
c. Nondeterminism
d. Unification
e. Turning transition graphs into regular expressions
f. Converting regular expressions into Finite Automata
D. Finite Automata with Output — 3 hours
a. Moore machines
b. Mealy machines
c. Moore = = Mealy
d. Examples
E. Regular languages — 3 hours
a. Closure properties
b. Complement and Intersection
c. Pumping Lemma

Part II: Theory of Formal Languages
F. Context-free Grammars — 5 hours
a. Define languages
b. Parse trees
c. The Total Language Tree of the CFG
d. Regular grammar
e. Ambiguity
f. Chomsky Normal Form
g. Derivations
G. Pushdown Automata — 5 hours
a. Building a PDA for a CFG
b. Building a CFG for a PDA
H. Context-free languages — 5 hours
a. Self embeddedness
b. Pumping lemma
c. Closure properties
d. Intersection and complement
e. Finiteness, emptiness and membership

Part III: Theory of Turing Machines
I. Turing Machines — 4 hours
a. Define Turing machine
b. Post Machines
c. Simulating PM on a TM
d. Simulating TM on PM
J. Variations of Turing Machines — 3 hours
a. The k-track TM
b. Recursively enumerable languages
c. Universal TM
d. Decidability
K. The Chomsky Hierarchy and Computers — 3 hours
a. Phrase structure grammar
b. Type 0=TM
c. Defining the computer
d. Church thesis
Midterm Exams — 2 hours

Total = 42 hours

Final Exam: During Final Exam week

Evaluation Methods

The final grade for the course is determined as follows:
Two class tests   30%
Final Exam    30%
Homework and Projects  25%
Quizzes    15%

Grading Scale:  90-100% — A, 80-89% — B, 70-79% — C, 60-69% — D, 0-59% — F

Attendance:

The attendance policy will conform to the universitywide attendance criteria.

Required Textbook

Introduction to Computer theory, Second Edition, Daniel I.A.  Cohen., John Wiley & Sons, Inc., New York, 1997

• Computer Science Department
• Stright Hall, Room 319
210 South Tenth Street
Indiana, PA 15705
• Phone: 724-357-2524
• Fax: 724-357-2724
• Office Hours
• Monday through Friday
• 7:30 a.m. – 12:00 p.m.
• 1:00 p.m. – 4:00 p.m.