Formal Languages and Automata Theory
OBJECTIVE:
• Introduce the scholar to the ideas of Theory of computation in applied science
• the scholars ought to acquire insights into the connection among formal languages, formal Grammars and automat.
UNIT – I:
Finite Automata Why Study Automata Theory? The Central ideas of Automata Theory, Automation, Finite Automation, Transition Systems, Acceptance of a String by a Finite Automation, DFA, style of DFAs, NFA, style of NFA, Equivalence of DFA and NFA, Conversion of NFA into DFA, Finite Automata with E-Transition, reduction of Finite Automata, sandy and Moore Machines, Applications and Limitation of Finite Automata.
UNIT – II:
Regular Expressions Regular Expressions, Regular Sets, Identity Rules, Equivalence of 2 Regular Expressions, Manipulations of standard Expressions, Finite Automata, and Regular Expressions, lay Conversion, Equivalence between Finite Automata and Regular Expressions, Pumping Lemma, Closers Properties, Applications of standard Expressions, Finite Automata and Regular Grammars, Regular Expressions and Regular Grammars.
UNIT – III:
Context Free synchronic linguisticss Formal Languages, Grammars, Classification of Grammars, A. Noam Chomsky Hierarchy Theorem, Context Free Grammar, left and right Derivations, take apart Trees, Ambiguous Grammars, Simplification of Context Free Grammars-Elimination of Useless Symbols, EProductions and Unit Productions, traditional kinds for Context Free Grammars-Chomsky traditional kind and Greibach traditional Form, Pumping Lemma, Closure Properties, Applications of Context Free Grammars.
UNIT – IV:
Pushdown Automata Pushdown Automata, Definition, Model, Graphical Notation, fast Description Language Acceptance of pushdown Automata, style of Pushdown Automata, settled and Non – settled Pushdown Automata, Equivalence of Pushdown Automata and Context Free Grammars Conversion, 2 Stack Pushdown Automata, Application of Pushdown Automata.
UNIT – V:
Turning Machine Turing machine, Definition, Model, illustration of Alan Turing Machines-Instantaneous Descriptions, Transition Tables and Transition Diagrams, Language of a Turing machine, style of Alan Turing Machines, Techniques for Turing machine Construction, sorts of Alan Turing Machines, Church’s Thesis, Universal Turing machine, Restricted Turing machine.
II Year – II Semester
L T P C
4 0 0 3
UNIT – VI:
Computability Decidable and Un-decidable issues, Halting drawback of Alan Turing Machines, Post’s Correspondence drawback, changed Post’s Correspondence drawback, categories of P and NP, NPHard and NP-Complete issues.
OUTCOMES:
• Classify machines by their power to acknowledge languages,
• use finite state machines to resolve issues in computing,
• justify settled and non-deterministic machines,
• Comprehend the hierarchy of issues arising within the applied science
TEXT BOOKS:
one. Introduction to Automata Theory, Languages and Computation, J.E.Hopcroft, R.Motwani and J.D.Ullman, third Edition, Pearson, 2008.
2. Theory of laptop Science-Automata, Languages and Computation, K.L.P.Mishra and N.Chandrasekharan, third Edition, PHI, 2007.
REFERENCE BOOKS:
one. Formal Language and Automata Theory, K.V.N.Sunitha and N.Kalyani, Pearson, 2015.
2. Introduction to Automata Theory, Formal Languages and Computation, Shyamalendu Kandar, Pearson, 2013.
3. Theory of Computation, V.Kulkarni, university Press, 2013.
4. Theory of Automata, Languages and Computation, Rajendra Kumar, handler Hill, 2014.