GATE and Engineering Theory Of Computation Handwritten Notes | Formal Language and Automata Theory

At the end of the pdf, the student will be able to:

– Understand the need and significance of computational theory, formal machines, languages and computations in computer engineering.

– Understand, design and analyze the role of finite automaton in recognizing a regular language.

–  Understand, analyze and apply the Context Free Grammar and Push-Down automaton with its advantages and limitations

–  Understand, analyze and design Turing machine model for computable languages with its strength and limitations.

–  Understand and analyze Universal Turing Machine and its undecidability issues. 

Mathematical preliminaries: Strings, alphabet, languages; Graphs and

Trees; Inductive proofs, set notation, Relations, Finite automata.

Regular expressions, Properties of regular sets: Pumping lemma,

closure properties and decision algorithm for regular sets.

Context Free Grammars. Properties of Context free languages (CFLs): Greibach‟s theorem, Pumping lemma, closure properties and decision algorithms for CFLs. Pushdown automata.

Turing machines: Turing machine model, computable languages and functions, techniques for turing machine construction, modification of turing machines, Halting problem of turing machine, church‟s hypothesis, turing machine as enumerators. Undecidability: Problems, properties of recursive and recursively enumerable languages, universal turing machines and undecidable problem, Rices‟ theorem, Post‟s correspondence problem, introduction to recursive functions theory.