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
