Name of Subject  : THEORY OF COMPUTATION (6 CS 5)

Unit

Content

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.

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.

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.

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.

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