Finite Automata and Regular Expressions, Properties of Regular Sets, Context-Free Grammars, Pushdown Automata, Turing Machines, Undecidability, The Chonsky Hierarchy, Computational Complexity Theory: Tractability and Intractability.

Semester:

August

Rationale:

To provide an exposure to the theory of formal languages, automata and complexity theory.

Catalog Description:

Finite Automata and Regular Expressions, Properties of Regular Sets, Context-Free Grammars, Pushdown Automata, Turing Machines, Undecidability, The Chonsky Hierarchy, Computational Complexity Theory: Tractability and Intractability.

Credits:

3(3-0)

Prerequisite:

None

Course Outline:

Finite Automata and Regular Expressions

1. Finite State Systems
2. Non-deterministic Finite Automata
3. Regular Expressions

Properties of Regular Sets

1. The Pumping Lemma for Regular Sets
2. Closure Properties of Regular Sets
3. Decision Algorithms for Regular Sets

Context-Free Grammars, Pushdown Automata

1. Derivation Trees
2. Simplication of Context-Free Grammars
3. Normal Forms
4. Pushdown Automata
5. Properties of Context-Free Languages: The Pumping Lemma for CFL's, Closure Properties of CFL's, Decision Algorithms for CFL's

Turing Machines

1. Computable Languages and Functions
2. Church's Hypothesis

Undecidability

1. Properties of Recursive and Recursively Enumerable Languages
2. Universal Turing Machines and Undecidable Problem
3. Recursive Function Theory

The Chonsky Hierarchy

Computational Complexity Theory: Tractability and Intractability

Textbook:

H.R. Lewis, C.H. Papadimitriou:

Element of the Theory of Computation, Prentice Hall, 2nd Edition, 1998.

Reference Books:

C. Calude:

Theories of Computational Complexity, North Holland, 1988.

M. Chandrasekaran, and K.L.P. Mishra:

Theory of Computer Science: Automata, Language and Computation, Prentice Hall, 1995.

J.E. Hopcroft, J.D. Ullman:

Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Massachusetts, 1979.

M. Sipser:

Introduction to the Theory of Computation, Pws Pub Co, USA, 1996.

C.H. Smith:

A Recursive Introduction to the Theory of Computation, Springer Verlag, 1994.

R.G. Taylor:

Model of Computation and Formal Languages, Oxford University Press, 1997.

M.R. Garey and D. S. Johnson:

Computer and Intractability, W.H. Freeman and Company, New York, 1979.

Grading System:

The final grade will be computed from the following constituent parts: mid-semester exam (30%) and final exam (70%).Open-book examination is used for both mid-semester and final exam. ~

Instructor:

Prof. Phan Minh Dung

Contact us: Olivier Nicole

Last update: Jul 2003