Periods/week : 3 Periods & 1 Tut /week.                                                                  Ses. : 30 Exam : 70 Examination (Practical): 3hrs.                                                                                   Credits: 4

1. Finite Automata and Regular Expressions:
Basic Concepts  of Finite State Systems, Deterministic and Non-Deterministic Finite Automata, Finite Automata with e-moves, Regular Expressions, Minimization of Finite Automata, Mealy and Moore Machines, Two-Way Finite Automate.

 

2. Regular sets & Regular Grammars:
Basic Definitions of Formal Languages and Grammars, Regular Sets and Regular Grammars, Closure Properties of Regular Sets, Pumping Lemma for Regular Sets, Decision Algorithm for Regular Sets, Myhill-Nerode Theorem, Minimization of Finite Automata.

3. Context Free Grammars and Languages:
Context Free Grammars and Languages, Derivation Trees, Simplification  of Context Free Grammars, Normal Forms, Pumping Lemma for CFL, closure properlties of CFL’s, Decision Algorithm for CFL.

4. Push down Automata and Deterministic CFL:
Informal Description, Definitions, Push-Down Automata and Context free Languages, Parsing and Push-Down Automata.

5. Universal Turing Machines and Undecidability:
Design and  Techniques for Construction  of Turing Machines,  Undecidability of PCP. Chomsky Hierarchy, Regular Grammars, Unrestricted Grammars, Context Sensitive languages,Relationship between classes of languages.

 

TEXT BOOKS:            Introduction to Automata Theory, Languages & Computation By J.E.Hopcraft & Jeffery D.Ulman – Narosa Publishing Company.

REFERENCE BOOKS: 
Theory of Computer Science By Mishra & Chandra
Sekharan, PHI.
An Introduction To Formal Languages and Automata,3e By  Peter Linz – Narosa Publishing House.

tejus mahiCSE 3.1 SyllabusIT 3.1 SyllabusCSE,CSE Syllabus,Formal Languages And Automata Theory Syllabus,IT,IT Syllabus
Periods/week : 3 Periods & 1 Tut /week.                                                                  Ses. : 30 Exam : 70 Examination (Practical): 3hrs.                                                                                   Credits: 4 1. Finite Automata and Regular Expressions: Basic Concepts  of Finite State Systems, Deterministic and Non-Deterministic Finite Automata,...