Theory of Computation (English)

Objectives, Introduction, Automaton, Finite Automata (FA), Model of Finite Automata, Finite Automata Notations, Finite Automata Representation, Acceptability of String by Finite Automata, Applications of Finite Automata, Types of Finite Automata, Deterministic Finite Automata (DFA), Definition of DFA, Nondeterministic Finite Automata (NFA/NDFA), Definition of NFA, Acceptability of String by NFA/NDFA, Significance of NFA/NDFA, Nondeterministic Finite Automata with ?-moves (Null Moves), ?-closure, Definition of ?-closure (Null Move), Definition of Nondeterministic Finite Automata with ?-Moves (Null Moves), Significance of NFA/NDFA with ?-moves (Null Moves), Comparison between DFA and NFA, Equivalence Between two Finite Automata’s, Converting NFA Without ?-Moves to its Equivalent DFA, Converstion of NFA with ?-moves to its Equivalent NFA without ?-moves, Conversion of NFA with ?-transition to its Equivalent DFA, Equivalence Between Two DFA?s, Relationship Between Regular Expression and Finite Automata, Minimization of Finite Automata, Finite Automata with Outputs, Representation of Finite Automata with Output, Types of Finite Automata With Output, Conversion of a Moore Machine to Mealy Machine, Conversion of a Mealy Machine to Moore Machine, Comparison between Moore Machine and Mealy Machine, Review Questions, Multiple Choice Questions, Answer Key.

 

2. Regular Grammar and Regular Expression

---

Objectives, Introduction, Formal Language, Grammar, Definition of a Grammar, Notations, Production Rules, Language Generated by Grammar G, Grammar Generated by Language L(G), Regular Language, Regular Grammar, Notations Used in Regular Grammar, Regular Expression, Meaning of the Notations Used in Above Rules of the Regular Expression, Building of Regular Expression, Identity Rules For Regular Expression, Regular Expression and Automata, Conversion of Regular Expression to Non Deterministic Finite Automata (NFA/NDFA), Conversion of Regular Expression to Deterministic Finite Automata, Conversion of Finite Automata Into a Regular Expression, Equivalence of Two Regular Expression, Regular Sets, Closure Properties of Regular Set, Pumping Lemma for Regular Sets, Myhill-Nerode Theorem, Decision Algorithm For Regular Sets, Review Questions, Multiple Choice Questions, Answer Key.

 

3. Context Free Grammars and Push Down Automata

---

Objectives, Introduction, Context Free Grammars, Definition, Derivation Tree (Parse Tree), Definition, Leftmost and Rightmost Derivations, Ambiguity in Context Free Grammars, Simplification of Context Free Grammar, Removing Null (Ù) Production, Reducing Grammar or Removing Useless Symbols, Removing Unit Productions, Designing Context Free Language From Context Free Grammar, Designing Context Free Grammar From Context Free Language, Basic Strategy For CFG Design, Normal Forms, Chomsky Normal Form (CNF), Greibach Normal Form (GNF), Pumping Lemma for Context Free Language, Properties of Context Free Languages, Push Down Automata, Basic Structure of Push Down Automata, Types of PDA, Acceptance by the PDA, Behavior of the PDA on Reading the String 0011, Instantaneous Description of a PDA (ID), Review Questions, Multiple Choice Questions, Answer Key.

 

4. Turing Machine

---

Objectives, Introduction, Basic Structure and Working of Turing Machine (TM), Formal Definition of a Turing Machine, Representation of Turing Machine, Instantaneous Description of TM, Transition Table Representation of Turing Machine, Transition Diagram Representation of Turing Machine, Language Acceptance by Turing Machine, Designing of Turing Machine, Turing Machine to Compute Functions, Modifications of Turing Machines, Multitrack Turing Machine, Multitape Turing Machine, Multidimensional Turing Machine, Nondeterministic Turing Machines (NTM/NDTM), Decidable and Undecidable Problems, Recursive and Recursive Enumerable Language, Definitions, Closure Properties of Recursive Language and Recursive Enumerable Language Class, Universal Turing Machine, Definition, Rice Theorem, Definition (Solvable or Decidable Problem), Review Questions, Multiple Choice Questions, Answer Key.

 

5. Linear Bounded Automata

---

Objectives, Introduction, Model of Linear Bounded Automata, Context Sensitive Grammar, Context Sensitive Languages, Properties of Context Sensitive Languages, Chomsky Classification of Languages and Grammars, Type-3 Grammar (Regular Grammar), Type-2 Grammar (Context Free Grammar), Type-1 Grammar (Context Sensitive Grammar), Type-0 Grammar (Unrestricted Grammar), Hierarchy of Language, Machine and Grammar, Linear Bounded Automata and Languages, Review Questions.