Course Details
Subject {L-T-P / C} : CS2004 : Formal Languages and Automata Theory { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Prof. Ramesh Kumar Mohapatra
Syllabus
Introduction to Automaton. Finite Automata and Regular Expressions: Deterministic and nondeterministic finite automata, regular expressions, Two way finite automata, finite automata with output: Mealy and Moore machines Properties of Regular Sets: Pumping lemma, closure properties, decision algorithm, MyHill- Nerode theorem and minimization of finite automata Context-Free Grammars (CFG): CFGs, derivation trees, simplification, Chomsky normal forms, Greibach normal forms Pushdown Automata(PDA): Definitions, relationship between PDA and context free languages Properties of Context-Free Languages: Pumping lemma, closure properties, decision algorithm Turing Machines: The Turing machine model, computable languages and functions, techniques for Turing machine construction, modification of Turing machines, church’s hypothesis, Turing machines as enumerators Un-decidability: properties of recursive and recursively enumerable languages, universal Turing machines, rice’s theorem, post correspondence problem Chomsky Hierarchy: regular grammars, unrestricted grammars, context sensitive languages, relations between classes of languages. P, NP, NP-complete, and NP Hard class of problems.
Course Objectives
- 1. To focus on the study of abstract models of computation. These abstract models allow the students to assess via formal reasoning what could be achieved through computing when they are using it to solve problems in science and engineering.
- 2. The course exposes students to the computability theory, as well as to the complexity theory. The goal is to allow them to answer fundamental questions about problems, such as whether they can or not be computed, and if they can, how efficiently.
- 3. The course introduces basic computation models and their properties, and the necessary mathematical techniques to prove more advanced attributes of these models.
Course Outcomes
The goal of this course is to provide students with an understanding of basic concepts in the theory of computation. At the end of this course students will be able to: <br />1. Construct finite state machines and the equivalent regular expressions. Prove the equivalence of languages described by finite state machines and regular expressions. <br />2. Construct pushdown automata and the equivalent context free grammars. Prove the equivalence of languages described by pushdown automata and context free grammars. <br />3. . Construct Turing machines and Post machines. Prove the equivalence of languages described by Turing machines and Post machines.
Essential Reading
- Jeffrey D Ullman, John E Hopcroft, Introduction to Automata Theory and Languages, Addison-Wesley , 1979.
- P. Linz, Introduction to Formal Language and Computation, Narosa , 2nd Ed, 2006.
Supplementary Reading
- Michael Sipser, Introduction to the Theory of Computation, PWS Pub. Co , 1996
- Mishra & Chandrasekharan, Theory of computer science: Automata language and computation, Prentice Hall of India , 3rd Ed, 2007