THEORY OF AUTOMATA AND FORMAL LANGUAGES (RCS403)

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

Click Here To Download

Upload your notes

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.

Share
Published by
uptusuccess

Recent Posts

Kasoor Lyrics | Prateek Kuhad

Haan Main Gumsum Hoon In Raahon Ki Tarah Tere Khwabon Mein Teri Khwahishon Mein Chupa Naa Jaane Kyu Hai Roz…

2 months ago

ARTIFICIAL INTELLIGENCE (NCS-702)

Download notes of ARTIFICIAL INTELLIGENCE (NCS-702) Click Here to Download Upload your notes Syllabus of ARTIFICIAL INTELLIGENCE (NCS-702) Unit-I 10Introduction…

3 months ago

OPERATION RESEARCH (NOE-073)

Download notes of OPERATION RESEARCH (NOE-073) Click Here   Upload your notes Syllabus of OPERATION RESEARCH (NOE-073) UNIT-I: Introduction: Definition…

4 months ago

Learn Angular 2 From Beginner To Advanced

What you'll learn Develop web applications using Angular 2 Create single-page applications Write cleaner and reusable code for better maintainability…

4 months ago

OPERATING SYSTEM (NCS-401)

Download notes of OPERATING SYSTEM (NCS-401) Click Here To Download Upload your notes Syllabus of OPERATING SYSTEM (NCS-401): Unit –…

4 months ago

COMPUTER GRAPHICS (NCS-403)

Download notes of COMPUTER GRAPHICS (NCS-403) Click Here To Download Upload your notes Syllabus of COMPUTER GRAPHICS (NCS-403): Unit –…

4 months ago

To join Facebook Group Click Here
To join Whatsapp GroupClick Here
To join G Plus Community Click Here