CS208

AUTOMATA AND FORMAL LANGUAGES 

Objectives

  • To introduce concepts in automata theory and theory of computation 
  • To identify different formal language classes and their relationships 
  • To design grammars and recognizers for different formal languages 

 

Outcomes

  • Ability to relate practical problems to languages, automata, and computability 
  • Ability to demonstrate an increased level of mathematical sophistication 
  • Ability to apply mathematical and formal techniques for solving problems 

 

Unit – I

Introduction- Alphabets, Strings and Languages; Automata and Grammars, Deterministic finite Automata (DFA)-Formal Definition, Simplified notation: State transition graph, Transition table, Language of DFA, Nondeterministic finite Automata (NFA), NFA with epsilon transition, Language of NFA, Equivalence of NFA and DFA, Minimization of Finite Automata, Distinguishing one string from other, Myhill-Nerode Theorem.

 

Unit – II

Regular Expression (RE)- Regular expression (RE) Definition, Operators of regular expression and their precedence, Algebraic laws for Regular expressions, Kleen’s Theorem, Regular expression to FA, DFA to  Regular expression, Arden Theorem, Non Regular Languages, Pumping Lemma for regular Languages. Application of Pumping Lemma, Closure properties of Regular Languages, Decision properties of Regular Languages, FA with output: Moore and Mealy machine, Equivalence of Moore and Mealy Machine, Applications and Limitation of FA. 

 

Unit – III

Context Free Grammar (CFG) and Context Free Languages (CFL)- Definition, Examples, Derivation, Derivation trees, Ambiguity in Grammar, Inherent ambiguity, Ambiguous to Unambiguous CFG, Useless symbols, Simplification of CFGs, Normal forms for CFGs: CNF and GNF, Closure proper ties of CFLs, Decision Properties of CFLs: Emptiness, Finiteness and Membership, Pumping lemma for CFLs.

 

Unit – IV

Push Down Automata (PDA)- Description and definition, Instantaneous Description, Language of PDA, Acceptance by Final state, Acceptance by empty stack, Deterministic PDA, Equivalence of PDA and CFG, CFG to PDA and PDA to CFG.

 

Unit – V

Turing machines (TM)- Basic model, definition and representation, Instantaneous Description, Language acceptance by TM, Variants of Turing Machine, TM as Computer of Integer functions, Universal TM, Chur ch’s Thesis, Recursive and recursively enumerable languages, Halting problem, Introduction to Undecidability, Undecidable problems about TMs. Post correspondence problem (PCP), Modified PCP, Introduction to recursive function theory.

 

TEXT BOOKS

  • Hopcroft and Ullman, “Introduction to Automata Theory, Languages and Computation”, Pearson Education, 3rd edition, 2006 

 

REFERENCE

  • Martin J. C., “Introduction to Languages and Theory of Computations”, TMH, 4th  edition, 2010 
  • Peter Linz, "An Introduction to Formal Language and Automata", Narosa Pub. House, 2011 
  • Papadimitriou, C. and Lewis, C. L., “Elements of the Theory of Computation”, PHI, 1997