Summary FLAT - A comprehensive study of machine

FORMAL LANGUAGES AND AUTOMATA THEORY 10CS56




FORMAL LANGUAGES AND AUTOMATA THEORY


Subject Code: 10CS56 I.A. Marks : 25
Hours/Week : 04 Exam Hours: 03
Total Hours : 52 Exam Marks: 100




PART - A
UNIT – 1
7 Hours
Introduction to Finite Automata: Introduction to Finite
Automata; Thecentral concepts of Automata theory; Deterministic
finite automata; Nondeterministic finite automata
UNIT – 2
7 Hours
Finite Automata, Regular Expressions: An application of finite
automata;Finite automata with Epsilon-transitions; Regular expressions;
Finite Automata and Regular Expressions; Applications of Regular
Expressions
UNIT – 3
6 Hours
Regular Languages, Properties of Regular Languages:
Regularlanguages; Proving languages not to be regular languages;
Closure properties of regular languages; Decision properties of
regular languages; Equivalence and minimization of automata
UNIT – 4
6 Hours
Context-Free Grammars And Languages : Context –free grammars;
Parsetrees; Applications; Ambiguity in grammars and Languages .
PART – B
UNIT – 5
7 Hours
Pushdown Automata: Definition of the Pushdown automata; the
languagesof a PDA; Equivalence of PDA‟s and CFG‟s; Deterministic
Pushdown Automata
UNIT – 6
6 Hours
Properties of Context-Free Languages: Normal forms for CFGs;
Thepumping lemma for CFGs; Closure properties of CFLs
UNIT – 7
7 Hours
Introduction To Turing Machine: Problems that Computers cannot
solve;The turning machine; Programming techniques for Turning Machines;
Extensions to the basic Turning Machines; Turing Machine and Computers.
UNIT – 8
6 Hours
Undecidability: A that is not recursively enumerable;
AnUndecidable problem that is RE; Post‟s Correspondence
problem; Other undecidable problems.


1

,FORMAL LANGUAGES AND AUTOMATA THEORY 10CS56



Text Books:
1. John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman:
Introduction to Automata Theory, Languages and Computation,
3rd Edition, Pearson Education, 2007.
(Chapters: 1.1, 1.5, 2.2 to 2.5, 3.1 to 3.3, 4, 5, 6, 7,
8.1 to 8.4, 8.6, 9.1, 9.2, 9.4.1, 9.5)
Reference Books:
1. K.L.P. Mishra: Theory of Computer Science, Automata,
Languages, and Computation, 3rd Edition, PHI, 2007.
2. Raymond Greenlaw, H.James Hoover: Fundamentals of the Theory
of Computation, Principles and Practice, Morgan Kaufmann, 1998.




2

,FORMAL LANGUAGES AND AUTOMATA THEORY 10CS56



Table Of Contents Page no


UNIT-1:INTRODUCTION TO FINITE AUTOMATA: 1
1.1: Introduction to finite Automata
1.2 : Central concepts of automata
theory 1.3: Deterministic finite automata
1.4:Non deterministic finite automata


UNIT-2:FINITE AUTOMATA, REGULAR EXPRESSIONS 18
2.1 An application of finite automata
2.2 Finite automata with Epsilon transitions
2.3 Regular expressions
2.4 Finite automata and regular expressions

2.5Applications of Regular expressions


UNIT- 3: PROPERTIES OF REGULAR LANGUAGES 34
3.1 Regular languages
3.2 proving languages not to be regular languages
3.3 closure properties of regular languages
3.4 decision properties of regular languages
3.5 equivalence and minimization of automata

UNIT-4:Context Free Grammar and languages 53
4.1 Context free grammars
4.2 parse trees
4.3 Applications
4.4 ambiguities in grammars and languages




3

, FORMAL LANGUAGES AND AUTOMATA THEORY 10CS56


UNIT-5: PUSH DOWN AUTOMATA 64
5.1: Definition of the pushdown automata
5.2: The languages of a PDA
5.3: Equivalence of PDA and CFG
5.4: Deterministic pushdown automata


Unit-6: PROPERTIES OF CONTEXT FREE LANGUAGES 74
6.1 Normal forms for CFGS
6.2The pumping lemma for CFGS
6.3closure properties of CFLS


UNIT -7: INTRODUCTION TO TURING MACHINES 94
7.1 problems that computers cannot solve
7.2 The Turing machine
7.3 Programming techniques for turing machines
7.4 Extensions to the basic turing machines
7.5 Turing machines and computers

Unit-8: Undesirability 104
8.1: A language that is not recursively enumerable
8.2: a un-decidable problem that is RE
8.3: Posts correspondence problem

8.4: Other undecidable problem




4