6 CS 5-THEORY OF COMPUTATION |
Units: I |
Finite Automata & Regular Expression: Basic Concepts of finite state system, Deterministic and non-deterministic finite
automation and designing regular expressions, relationship between regular expression & Finite automata minimization of
finite automation mealy & Moore Machines.
|
Units: II |
Regular Sets of Regular Grammars: Basic Definition of Formal Language and Grammars. Regular Sets and Regular
Grammars, closure proportion of regular sets, Pumping lemma for regular sets, decision Algorithms for regular sets,
Myhell_Nerod Theory & Organization of Finite Automata. |
Units: III |
Context Free Languages& Pushdown Automata: Context Free Grammars – Derivations and Languages –
Relationship between derivation and derivation trees – ambiguity – simplification of CEG – Greiback Normal form –
Chomsky normal forms – Problems related to CNF and GNF Pushdown Automata: Definitions – Moves –
Instantaneous descriptions – Deterministic pushdown automata – Pushdown automata and CFL - pumping lemma for CFL -
Applications of pumping Lemma.
|
Units: IV |
Turing Machines: Turing machines – Computable Languages and functions – Turing Machine constructions – Storage in
finite control – multiple tracks – checking of symbols – subroutines – two way infinite tape. Undecidability: Properties of
recursive and Recursively enumerable languages – Universal Turing Machines as an undecidable problem – Universal
Languages – Rice’s Theorems.
|
Units: V |
Linear bounded Automata Context Sensitive Language: Chomsky Hierarchy of Languages and automata, Basic Definition &
descriptions of Theory & Organization of Linear bounded Automata Properties of context-sensitive languages.
|