Hii sir, I Wants to get the Syllabus and Question Paper of the Theory Of Automata And Formal Languages Subject of the B.tech Information Technology Course of the UPTU University ?

As you Asking for the Syllabus and Question Paper of the Theory Of Automata And Formal Languages Subject of the B.tech Information Technology the Syllabus and the Question Paper is given below

Syllabus


THEORY OF AUTOMATA AND FORMAL LANGUAGES
Unit – I
Introduction; Alphabets, Strings and Languages; Automata and Grammars, Deterministic finiteAutomata (DFA)-Formal Definition, Simplified notation: State transition graph, Transition table, Language of DFA, Nondeterministic finite Automata (NFA), NFA with epsilon transi ion,Language of NFA, Equi valence of NFA and DFA, Minimization of Finite Automata, Distinguishing one string from other, Myhill-Nerode Theorem


Unit – II
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 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 Memership, 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 Computerof 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 .


the Question Paper of the Theory Of Automata And Formal Languages Subject of the B.tech Information Technology Course of the UPTU University is given below

Theory Of Automata And Formal Languages Subject of the B.tech Information Technology Course