I. Strings, alphabets and languages - Graphs and trees finite automata and regular expression - finite state systems - Non deterministic finite automata - finite automata with E-moves - regular expression.

II. Tow-way finite automata - finite automata with output - Pumping lemma for regular sets - closure properties of regular sets - Decision algorithms for regular sets - The Myhill - Nerode therorem and minimuzation of finite automata.

III. Context - free grammars - Motivation and introduction - context free grammars - derivation trees - Chomosky normal form - Greibach normal form push down automata, properties of CFL.

IV. Truing machines - Introduction - Truing machine model - computable languages and functions - Church's hypothesis - Regular grammars - Unrestricted grammars - Context - Sensitive languages - Chomosky hierarchy.

Text Book :
John E. Hopcroft and Jeffery D. Ullman introduction to Automata theory, languages and computation, Narosa Publishing house New Delhi, 1994.