JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY 
HYDERABAD 
III Year B.Tech. CSE -I Sem T P C 
4+1* 0 4 
FORMAL LANGUAGES AND AUTOMATA THEORY 

 The purpose of this course is to acquaint the student with an overview of the theoretical foundations 
of computer science from the perspective of formal languages. 
• Classify machines by their power to recognize languages. 
• Employ finite state machines to solve problems in computing. 
• Explain deterministic and non-deterministic machines. 
• Comprehend the hierarchy of problems arising in the computer sciences. 

UNIT I : 
Fundamentals : Strings, Alphabet, Language, Operations, Finite state machine, definitions, finite 
automaton model, acceptance of strings, and languages, deterministic finite automaton and non 
deterministic finite 
automaton, transition diagrams and Language recognizers. 

UNIT II : 
Finite Automata : NFA with Î transitions - Significance, acceptance of languages. Conversions and 
Equivalence : Equivalence between NFA with and without Î transitions, NFA to DFA conversion, 
minimisation of FSM, equivalence between two FSM’s, Finite Automata with output- Moore and Melay 
machines. 

UNIT III : 
Regular Languages : Regular sets, regular expressions, identity rules, Constructing finite Automata for 
a given regular expressions, Conversion of Finite Automata to Regular expressions. Pumping lemma of 
regular sets, closure properties of regular sets (proofs not required). 

UNIT IV : 
Grammar Formalism : Regular grammars-right linear and left linear grammars, equivalence between 
regular linear grammar and FA, inter conversion, Context free grammar, derivation trees, sentential 
forms. 
Right most and leftmost derivation of strings. 

UNIT V : 
Context Free Grammars : Ambiguity in context free grammars. Minimisation of Context Free 
Grammars. Chomsky normal form, Greiback normal form, Pumping Lemma for Context Free 
Languages. Enumeration of properties of CFL (proofs omitted). 

UNIT VI : 
Push Down Automata : Push down automata, definition, model, acceptance of CFL, Acceptance by 
final state and acceptance by empty state and its equivalence. Equivalence of CFL and PDA, 
interconversion. (Proofs not required). Introduction to DCFL and DPDA. 

UNIT VII : 
Turing Machine : Turing Machine, definition, model, design of TM, Computable functions, recursively 
enumerable languages. Church’s hypothesis, counter machine, types of Turing machines (proofs not 
required). 

UNIT VIII 
Computability Theory : Chomsky hierarchy of languages, linear bounded automata and context 
sensitive language, LR(0) grammar, decidability of, problems, Universal Turing Machine, undecidability 
of posts. Correspondence problem, Turing reducibility, Definition of P and NP problems, NP complete 
and NP hard problems. 

TEXT BOOKS : 
1. “Introduction to Automata Theory Languages and Computation”. Hopcroft H.E. and Ullman J. D. 
Pearson Education 
2. Introduction to Theory of Computation –Sipser 2nd edition Thomson 

REFERENCES : 
1. Introduction to Computer Theory, Daniel I.A. Cohen, John Wiley. 
2. Introduction to languages and the Theory of Computation ,John C Martin, TMH 
3. “Elements of Theory of Computation”, Lewis H.P. & Papadimition C.H. Pearson /PHI. 
4 Theory of Computer Science – Automata languages and computation -Mishra and Chandrashekaran, 
2nd edition, PHI