# Download notes of THEORY OF AUTOMATA AND FORMAL LANGUAGES (RCS403)

**Syllabus of THEORY OF AUTOMATA AND FORMAL LANGUAGES (RCS403):**

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 transition, 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), 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 Grammar, 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 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.

**References:**

1. Hopcroft, Ullman, “Introduction to Automata Theory, Languages and Computation”,

Pearson Education.

2. KLP Mishra and N. Chandrasekaran, “Theory of Computer Science: Automata,

Languages and Computation”, PHI Learning Private Limited, Delhi India.

3. Peter Linz, “An Introduction to Formal Language and Automata”, Narosa Publishing

house.

4. YN Singh “Mathematical Foundation of Computer Science”, New Age International.

5. Malviya, AK “Theory of Computation and Application”, BPaperback Publications

6. Papadimitrou, C. and Lewis, CL, “Elements of the Theory of Computation”, Pearson

Publication.

7. K. Krithivasan and R. Rama; Introduction to Formal Languages, Automata Theory

and Computation; Pearson Education.

8. Harry R. Lewis and Christos H. Papadimitriou, Elements of the theory of

Computation, Second Edition, Prentice-Hall of India Pvt. Ltd.

9. Micheal Sipser, “Introduction of the Theory and Computation”, Thomson Learning.

10. Katuri Viswanath, “Introduction to Mathematical Computer Science, An” Universities

Press.