ANNA UNIVERSITY, CHENNAI
AFFILIATED INSTITUTIONS
REGULATIONS – 2017
CHOICE BASED CREDIT SYSTEM
CS8501 Theory Of Computation

UNIT I AUTOMATA FUNDAMENTALS 

Additional forms of Proof

Non-deterministic Finite Automata

Finite Automata with Epsilon Transitions

UNIT II REGULAR EXPRESSIONS AND LANGUAGES
Proving Languages not to be regular

Closure Properties of Regular Languages

Equivalence and Minimization of Automata.

UNIT III CONTEXT FREE GRAMMAR AND LANGUAGES 
CFG

Languages of a Pushdown Automata

Equivalence of Pushdown Automata and CFG, Deterministic Pushdown Automata.

UNIT IV PROPERTIES OF CONTEXT FREE LANGUAGES 
Normal Forms for CFG

Pumping Lemma for CFL

Turing Machines

UNIT V UNDECIDABILITY  
Undecidable Problem with RE

Undecidable Problems about TM

Post‘s Correspondence Problem.