Course

Unit I

Finite Automata (FA): Introduction, Deterministic Finite Automata (DFA) -Formal definition, simpler notations (state transition diagram, transition table), the language of a DFA. Nondeterministic Finite Automata (NFA)- Definition of the FA, language of an NFA, Equivalence of Deterministic and Nondeterministic Finite Automata, Applications of Finite Automata, Finite Automata with Epsilon Transitions, Eliminating Epsilon transitions, Minimization of Deterministic Finite Automata, Finite automata with output (Moore and Mealy machine Interconversion.

Unit II

Regular Expressions (RE): Introduction, Identities of Regular Expressions, Finite Automata and Regular Expressions- Converting from DFA’s to Regular Expressions, Converting Regular Expressions to Automata, applications of Regular Expressions. REGULAR GRAMMARS: Definition, regular grammar and FA, FA for regular grammar, Regular grammar for FA. Proving languages to be non-regular -Pumping lemma, applications, Closure properties of regular languages.

Unit III

Context Free Grammar (CFG): Derivation Trees, Sentential Forms, Rightmost and Leftmost derivations of Strings. Ambiguity in CFGs, Minimization of CCFGs CNF, GNF, Pumping Lemma for CFLs Enumeration of Properties of CFL

Unit IV

Pushdown Automata: Definition, Model, Acceptance of CFL, Acceptance by Final State and Acceptance by Empty stack and its Equivalence, Equivalence of CFG and PDA. TURING MACHINES (TM): Formal definition and behavior, Languages of a TM, TM as accepters, and TM as a computer of integer functions, Types of TMs.

Unit V

Recursive And Recursively Enumerable Languages (REL): Properties of recursive and recursively enumerable languages, Universal Turing machine, The Halting problem, Undecidable problems about TMs. Context-sensitive language and linear bounded automata (LBA), Chomsky hierarchy, Decidability, Post’s correspondence problem (PCP), undecidability of PCP.

Course Description 

Formal languages and automata theory deals with the concepts of automata, formal languages, grammar, computability and decidability. The reasons to study. Automata Theory possesses a high degree of permanence and stability, in contrast with the ever-changing paradigms of the technology, development, and management of computer systems.

Course Objectives

This course gives an overview of the theoretical foundations of computer science from the perspective of formal languages. Formal Languages and Automata Theory provide a simple, elegant view of the complex machine we call a computer. Further, parts of the Automata theory have a direct bearing on circuit design, compiler design, and search algorithms.

Course Outcomes

CO-PO Mapping

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2007), Introduction to Automata Theory Languages and Computation, 3rdedition, Pearson Education, India.
• Martin, John C., Introduction to Languages and the Theory of Computation, 3rd ed., Tata McGraw Hill Education Private Limited.
• H.R.Lewis and C.H.Papadimitriou, ―Elements of the theory of Computation‖, Second Edition, PHI, 2003.
• Micheal Sipser, ―Introduction of the Theory and Computation‖, Thomson Brokecole, 1997.
• Peter Linz, “An Introduction to Formal Languages and Automata”, Third Edition, 2002.