|Theory of Automata & Formal Language||Learning Schedule|
This course introduces some fundamental concepts in automata theory and formal languages including grammar, finite automaton, regular expression, formal language, pushdown automaton and Turing machine. This subject not only forms the basic models of computation, it also includes the foundation of many branches of computer science, e.g. compilers, software engineering, concurrent systems, etc. The properties of these models will be studied and various rigorous techniques for analysing and comparing them will be discussed, by using both formalism and examples.
- introduce the student to the concepts of theory of computation in computer science.
- acquire insights into the relationship among formal languages, formal grammars, and automata.
- learn to design automats and Turing machine
- demonstrate an understanding of abstract models of computing, including deterministic (DFA), non-deterministic (NFA), and Turing (TM) machine models.
- demonstrate an understanding of regular expressions and grammars, including context-free and context-sensitive gram-mars.
- understand the relationships between language classes, including regular, context-free, context-sensitive, recursive, and recursively enumerable languages.
- able to design Turing Machine
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 transit ion, 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 39 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) & Context Free Languages CFL)
Definition, Examples, Derivation, Derivation trees, Ambiguity in Grammer, 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, Two stack PDA.
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, Church’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.
- Theory of Computer Science : Automata, Languages and Computation – K.L.P. Mishra and N.Chandrasekaran,”, PHI
- Introduction to Languages and Theory of Computations – Martin J. C., TMH
- Introduction to Automata Theory, Languages and Computation – Hopcroft, Ullman, Pearson Education
- Elements of the Theory of Computation – Papadimitrou, C. and Lewis, C.L, PHI