UNIT I: FUNDAMENTALS OF AUTOMATA

1.1 Fundamentals of Automata- Computation, Finite State Machine

1.2 Components of Finite State Automata

1.3 Elements of Finite State System, Mathematical representation of Finite State Machine

1.4 Automata Classification, Automata in Real World

UNIT II: FORMAL LANGUAGE THEORY AND FORMAL LANGUAGES/ GRAMMAR HIERARCHY

2.1 Formal Language Theory- Symbols, Alphabets and Strings, Operations on Strings, Formal Languages, Operations on Languages

2.2 Formal Languages/ Grammar Hierarchy: Formal Languages, Regular Language, Context-Free Language, Context-Sensitive Language, Recursive Language, Recursively Enumerable Language, Other Forms of Formal Languages

2.3 Relationship between Grammars and Languages

UNIT III: FINITE AUTOMATA AND EQUIVALENT AUTOMATA

3.1 Finite Automata: Introduction, Deterministic Finite Automata(DFA), Design of DFAs, Non Deterministic Finite Automata(NFA), Non-Deterministic Automata with Є-moves ,Design of NFA- Є s, Advantages of Non-Deterministic Finite Automata, NFA Versus DFA

3.2 Equivalent Automata: Equivalent Finite-State Automata, Equivalence of NFA/NFA- ɛ and DFA, Equivalence of NFA, with Є moves to NFA, without Є - moves.

UNIT IV: MINIMIZATION/ OPTIMIZATION OF DFA, REGULAR EXPRESSIONS AND LANGUAGES AND FINITE AUTOMATA AND REGULAR EXPRESSIONS

4.1 Minimization/ Optimization of DFA: Optimum DFA, Minimal DFA

4.2 Two way DFA, DFA Vs 2DFA

4.3 Regular Expressions and Languages:Regular languages, Regular expressions, Components of Regular Expression,Properties of Regular Expressions, Uses of Regular Expressions.

4.4 Finite Automata and Regular Expressions:Properties of Regular Sets and Regular Languages, Arden’s Theorem

4.5 Equivalence of Finite Automata and Regular Expressions, Equivalence of DFA and Regular Expression, Equivalence of NFA and Regular Expression

UNIT V: TRANSDUCERS, CONTEXT-FREE GRAMMARS AND CONTEXT-FREE LANGUAGES AND SIMPLIFICATION OF CONTEXT – FREE GRAMMAR

5.1 Transducers: Moore Machine, Mealy Machine, Difference between Moore and Mealy Machines, Properties / Equivalence of Moore and Mealy Machines

5.2 Context-Free Grammars and Context-Free Languages: Types of Grammar, Ambiguous and Unambiguous Grammars, Noam Chomsky’s Classification of Grammar and Finite Automata, Relation between Regular Grammar and Finite Automata

5.3 Simplification of Context – Free Grammar: Simplification of Context-Free Grammars, Elimination of Є -Productions

5.4 Elimination of Unit Productions, Normal Forms for Context Free Grammars, Chomsky Normal Form, Greibach Normal Form, Chomsky Vs Greibach Normal Form, Application of Context- Free Grammars

UNIT VI: TURING MACHINE AND TM EXTENSIONS AND LANGUAGES

6.1 Turing Machine: Introduction, Components of Turing Machine, Description of Turing Machine,

6.2 Elements of TM, Moves of a TM, Language accepted by a TM, Role of TM’s , Design of TM’s

6.3 TM Extensions and Languages: TM Languages, Undecidable Problem, P and NP Classes of Languages