Finite Automata and Regular Expressions. Properties of Regular Sets. Context-Free Grammars. Pushdown Automata. Properties of Context-Free Languages. Turing Machines. Undecidability. Computational Complexity Theory. Intractable Problems.

Term

January

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. Properties of Context-Free Languages. Turing Machines. Undecidability. Computational Complexity Theory. Intractable Problems.

Credit

3(3-0)

Pre-requisite(s)

Consent of Instructor

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

1. Derivation Trees
2. Simplication of Context-Free Grammars
3. Normal Forms

Pushdown Automata

1. Pushdown Automata and Context-Free Languages

Properties of Context-Free Languages

1. The Pumping Lemma for CFL's
2. Closure Properties of CFL's
3. 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

Computational Complexity Theory

Intractable Problems

1. Polynomial Time and Space
2. NP-Complete Problems

Textbook(s)

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

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

References

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.

Grading system

The final grade will be computed from the following constituent parts: mid-term exam (25%), final exam (55%) and assignments/projects (20%). Open-book examination is used for both mid-term and final exam.

Instructor

Prof. Phan Minh Dung

Contact us: Olivier Nicole

Last update: Jan 1970