JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY ANANTAPUR
B. Tech II - II sem (C.S.E) T Tu C
3 1 3
(15A05404) FORMAL LANGUAGES AND
AUTOMATA THEORY
|
|||
Course
Objective:
|
|||
·
Understand
formal definitions of machine models.
·
Classify
machines by their power to recognize languages.
·
Understanding
of formal grammars, analysis
·
Understanding
of hierarchical organization of problems depending on their complexity
·
Understanding
of the logical limits to computational capacity
·
Understanding
of undecidable problems
Learning Outcome:
At the end of the course,
students will be able to
·
Construct
finite state diagrams while solving problems of computer science
·
Find
solutions to the problems using Turing machines
·
Design
of new grammar and language
UNIT I
Introduction:
Basics of set
theory, Relations on sets, Deductive proofs, Reduction to definitions, Other
theorem forms, Proving equivalences about sets, The Contrapositive, Proof by
contradiction, Counter examples, Inductive proofs, Alphabets, Strings,
Languages, Problems, Grammar formalism, Chomsky Hierarchy
Finite
Automata: An
Informal picture of Finite Automata, Deterministic Finite Automata (DFA), Non
Deterministic Finite Automata (NFA), Applying FA for Text search, Finite
Automata with
Epsilon
transitions (є-NFA or NFA- є ), Finite Automata with output, Conversion of one
machine to another, Minimization of Finite Automata, Myhill-Nerode Theorem.
UNIT II
Regular Languages:
Regular Expressions
(RE), Finite Automata
and Regular Expressions,
Applications
of Regular Expressions, Algebraic laws for Regular Expressions, The Arden‘s
Theorem, Using Arden‘s theorem to construct RE from FA, Pumping Lemma for RLs,
Applications of Pumping Lemma, Equivalence of Two FAs, Equivalence of Two REs,
Construction of Regular Grammar from
RE, Constructing FA from Regular
Grammar, Closure properties of RLs, Decision problem‘s of RLS,
Applications of REs and FAs
UNIT III
Context
Free Grammars and Languages: Definition
of Context Free Grammars (CFG), Derivations and Parse trees, Ambiguity
in CFGs, Removing ambiguity, Left recursion and Left factoring, Simplification
of CFGs, Normal Forms, Linear grammars, Closure properties for CFLs, Pumping
Lemma for CFLs, Decision problems for CFLs, CFG and Regular Language..
UNIT IV
Push
Down Automata (PDA): Informal
introduction, The Formal Definition, Graphical notation, Instantaneous
description, The Languages of a PDA, Equivalence of PDAs and CFGs,
Deterministic Push Down Automata, Two Stack PDA.
UNIT V
Turing
Machines and Undecidability: Basics
of Turing Machine (TM), Transitional Representation of TMs,
Instantaneous description, Non Deterministic TM, Conversion of Regular
Expression to TM, Two stack PDA and TM, Variations of the TM, TM as an integer
function, Universal TM, Linear Bounded Automata, TM Languages, Unrestricted
grammar , Properties of Recursive and Recursively enumerable languages,
Undecidability, Reducibility, Undeciadable problems about TMs, Post‘s
Correspondence Problem(PCP),
Modified PCP.
Text Books:
1. Introduction
to Automata Theory, Formal Languages and Computation, Shyamalendu kandar,
Pearson.
- Introduction
to Automata Theory, Languages, and Computation, Third Edition, John
E.Hopcroft, Rajeev Motwani, Jeffery D. Ullman, Pearson.
Reference Books:
1. Introduction to Languages and the
Theory of Computation, John C Martin, TMH, Third Edition.
2. Theory of Computation, Vivek
Kulkarni, OXFORD.
3. Introduction to the Theory of
Computation., Michel Sipser, 2nd Edition, Cengage Learning
4. Theory of computer Science
Automata, Languages and Computation, K.L.P. Mishra, N.
Chandrasekaran, PHI, Third Edition.
5. Fundamentals of the Theory of
Computation, Principles and Practice, Raymond Greenlaw, H. James Hoover,
Elsevier, Morgan Kaufmann.
Finite
Automata and Formal Language A Simple Approach, A.M. Padma Reddy, Pearson
