# Theory of Computation GTU Technical Book Pdf

UNIT – I Finite State Machines
Basic Concepts: Symbols, Strings, Language, Formal Language, Natural Language. Basic Machine and Finite State Machine.
FSM without Output: Definition and Construction-DFA, NFA, NFA with epsilon-Moves, Minimization Of FA, Equivalence of NFA and DFA, Conversion of NFA with epsilon moves to NFA, Conversion of NFA With epsilon moves to DFA.
FSM with Output: Definition and Construction of Moore and Mealy Machines, Inter-conversion between Moore and Mealy Machines. (Chapter – 1)

UNIT – II Regular Expressions
Definition and Identities of Regular Expressions, Construction of Regular Expression of the given L, Construction of Language from the RE, Construction of FA from the given RE using direct method, Conversion of FA to RE using Arden’s Theorem, Pumping Lemma for RL, Closure properties of RLs, Applications of Regular Expressions. (Chapter – 2)

UNIT – III Context-Free Grammar and Languages
Introduction, Formal Definition of Grammar, Notations, Derivation Process: Leftmost Derivation, Rightmost Derivation, derivation trees, Context-Free Languages, Ambiguous CFG, Removal of ambiguity, Simplification of CFG, Normal Forms, Chomsky Hierarchy, Regular grammar, the equivalence of RG(LRG and RLG) and FA. (Chapter – 3)

UNIT – IV Pushdown Automata and Post Machines
Push Down Automata: Introduction and Definition of PDA, Construction (Pictorial/ Transition diagram) of PDA, Instantaneous Description and ACCEPTANCE of CFL by empty stack and final state, Deterministic PDA Vs Nondeterministic PDA, Closure properties of CFLs, pumping lemma for CFL. Post Machine – Definition and construction. (Chapter – 4)
UNIT – V Turing Machines
A formal definition of a Turing machine, Recursive Languages and Recursively Enumerable Languages, Design of Turing machines, Variants of Turing Machines: Multi-tape Turing machines, Universal Turing Machine, Nondeterministic Turing machines. Comparisons of all automata. (Chapter – 5)

For Gtu Study Material and Paper solution: www.gtustudy.in