Theory of Computations

Duration: Approximately 30 Lecture hours

Pre-requisites: None

Learning Objectives

1. To introduce the mathematical formalisms of formal languages, finite automata, push downautomata and Turing machines.
2. To explain their applications to computer languages and compilers.
3. To provide exposure to the theory of complexity and intractable problems.

Course Content

1. Mathematical Preliminaries
2. Alphabets and Languages
3. Finite automata
4. Context free languages
5. Turing Machines
6. Computational Complexity

Learning Outcomes

1. At the end of this course, the students will be able to
2. Define and manipulate strings.
3. Define languages; and perform language operations.
4. Define and identify regular languages; and represent them finitely.
5. Define a deterministic finite automaton; and describe its operation.
6. Define a nondeterministic finite automaton; and describe its operation.
7. Explain the relationship between regular languages and finite automata.
8. Construct finite automata accepting regular languages.
9. Define and identify context free grammars and languages.
10. Define a pushdown automaton; and describe its operation.
11. Relate context free languages with pushdown automata.
12. Construct pushdown automata accepting context free languages.
13. Explain and apply Pumping lemma.
14. Define a Turing machine; and describe its operation.
15. Describe the computation with Turing machine

References

1. H.R. Lewis, C.H. Papadimitrio. Elements of the Theory of Computation. Prentice Hall. 2nd Edition,1998

2. D.C. Kozen. Automata and Computability, Springer-Verlang, New York, 1997