Theory of Automata & Formal Languages
⦁ OVERVIEW OF THE COURSE
Name of Course Theory of Automata & Formal Languages
Offering Department COMPUTER SCIENCE & ENGINEERING
OVERVIEW:
The Course on Theory of Automata & Formal Languages is offered to the second-year
students. Theory of Automata & Formal Languages course is to introduce the fundamental
mathematical and computational principles that are the foundation of computer science.
These include topics such as Turing machines, Automata, grammars and formal languages,
decidability, halting problem, the P, NP question and NP-Completeness reductions. Students
understand the fundamental theorems and proofs of theory provide the foundation material
for all specialties of computer science. For example, Theory of Automata & Formal
Languages introduces conceptual tools that practitioner’s use in compiler and programming
language. Theory of Automata & Formal Languages course prepares students for graduate
school and approximately 1/3 of the problems in GATE test for computer science require an
understanding of Theory of Automata & Formal Languages.
⦁ SYLLABUS
TITLE OF THE COURSE PRE-
COURSE NO
COURSE STRUCTURE REQUISITE
Theory of Automata & 3L - 1T - 0P None
COCSC 401
Formal Languages
COURSE OUTCOMES (COs)
After completion of this course, the students are expected to be able to demonstrate the
following knowledge, skills, and attitudes:
CO1: Understand formal languages, grammars, and automata, and analyze their relationships
with computational models.
CO2: Apply concepts of finite automata and regular expressions to design and optimize
regular language recognizers.
CO3: Construct context-free grammars and pushdown automata for context-free languages,
and solve problems related to ambiguity and normal forms.
CO4: Analyze and design Turing machines to model complex computational problems and
understand the limitations of computation.
CO5: Evaluate decidability and computational complexity of problems, distinguishing
between tractable and intractable problems, and explore P, NP, and NP-hard classifications.
1
COURSE CONTENTS
Unit I
Finite Automata and Regular Languages: Deterministic FA, Non-deterministic FA,
Regular expressions, Finite Automaton with €- moves, Regular Expression, Regular
Languages and Kleene’s theorem– Conversion of NFA to DFA, Equivalence of finite
Automaton and regular expressions, Arden’s Theorem. Myhill Nerode Theorem,
Minimization of DFA, Pumping Lemma for Regular sets, Problems based on Pumping
Lemma
Unit II
Context-Free Grammar and Languages: Grammar, Types of Grammar, Context Free
Grammars and Languages, Derivations, Ambiguity, Relationship between derivation and
derivation trees, Simplification of CFG, Elimination of Useless symbols - Unit productions -
Null productions, Chomsky normal form (CNF), Greibach Normal form (GNF), Problems
related to CNF and GNF
Unit III
Pushdown Automata and Context-Free Languages: Moves, Instantaneous descriptions,
Deterministic/Non-deterministic, pushdown automata, Equivalence of Pushdown automata
and CFL, pumping lemma for CFL, problems based on pumping Lemma, Conversion from
CFG-to-PDA, Conversion from PDA-to-CFG
Unit IV
Turing Machines and Computability: Definition and Types of Turing machines,
Computable languages and functions, Techniques for Turing machine construction, Multi
head and Multi tape Turing Machines, The Halting problem, Partial Solvability, Problems
about Turing machine- Chomsky hierarchy of languages
Unit V
Decidable and Undecidable Problems in Computability: Unsolvable Problems and
Computable Functions, Recursive and recursively enumerable languages, Universal Turing
machine, Measuring and classifying complexity - Tractable and Intractable problems, P, NP
and NP hard, Decidable and Undecidable problems
2
SUGGESTED READINGS
⦁ Hopcroft J.E., Motwani R. and Ullman J.D, “Introduction to Automata Theory,
Languages and Computations”, Second Edition, Pearson Education.
⦁ John C Martin, “Introduction to Languages and the Theory of Computation”, Third
Edition, Tata McGraw Hill Publishing Company, New Delhi
⦁ Marvin L. Minsky “Computation: Finite and Infinite” – Prentice Hall, 1967
⦁ Michael Sipser “Introduction to the Theory of Computation”, Third Edition, 2012
Cengage Learning
⦁ Peter Lenz – An Introduction to Formal languages and Automata – 3rd Edition
Narosa, 2003
⦁ Thomas A. Sukamp – An introduction to the theory of computer science languages
and machines – 3rd edition, Pearson Education, 2007.
⦁ G E Reevsz -“Introduction to Formal Languages” TMH, 2000.
D. THEORY LECTURE PLAN
NUMBER
S.
CONTENT OF Unit
No.
LECTURES
1 Unit-I
(11)
1 Introduction & Motivation of TOC, Infinite Sets, Closures,
Alphabets, Languages & Representation
2 Finite Automata: Deterministic FA 1
3 Nondeterministic FA 1
4 Regular expressions 1
5 Finite Automaton with €- moves 1
3
2 Finite Automata: Deterministic FA 1
3 Nondeterministic FA 1
4 Regular expressions 1
5 Finite Automaton with €- moves 1
Regular Expression, Regular Languages and Kleene’s 1
6
theorem– Conversion of NFA to DFA
Equivalence of finite Automaton and regular expressions, 2
7
Minimization of DFA
8 Arden’s Theorem. Myhill Nerode 1
9 Pumping Lemma for Regular sets, Problems based on 2
Pumping Lemma
CLASS TEST-I
10 Context Free Grammar: Grammar, Types of Grammar 1 Unit-
II
11 Context Free Grammars and Languages, Derivations, Ambiguity 1
(6)
12 Relationship between derivation and derivation trees 1
Elimination of Useless symbols - Unit productions - Null 1
13
productions
14 Chomsky normal form (CNF), 1
Greibach Normal form (GNF), Problems related to CNF and 1
15
GNF
Pushdown Automata Moves, Instantaneous descriptions, 2 Unit-
16
Deterministic/non-deterministic pushdown automata III
17 Conversion from CFG-to-PDA 1 (7)
18 1
Conversion from PDA-to-CFG
MID SEMESTER EVALUATION
19 Equivalence of Pushdown automata and CFL 1
Pumping lemma for CFL, problems based on pumping Lemma 2
20
Definition and Types of Turing machines, Computable 2 Unit-
21
languages and functions IV
22 Techniques for Turing machine construction 2 (9)
23 Multi head and Multi tape Turing Machines 1
4
Definition and Types of Turing machines, Computable 2 Unit-
21
languages and functions IV
22 Techniques for Turing machine construction 2 (9)
23 Multi head and Multi tape Turing Machines 1
The Halting problem, Partial Solvability 1
24
25 Problems about Turing machine 2
Unit-
26 Chomsky hierarchy of languages 1 V
27 Unsolvable Problems and Computable Functions 1 (7)
28 Recursive and recursively enumerable languages 1
29 Universal Turing machine 1
Measuring and classifying complexity - Tractable and 1
30
Intractable problems
31 Church-Turing Thesis & Universal Turing machines 1
32 P, NP and NP-hard problems 1
33 Decidable and Undecidable problems 1
E. SELF STUDY
Sr. Topic Unit
No
.
1 (i)How Vedic or philosophical concepts might challenge, inspire, or provide Unit I
insight into traditional computational theory?
(ii)How does the deterministic nature of finite automata (DFA) reflect the
Vedic concept of following a clear, preordained path (Svadharma), where every
decision is predetermined and fixed?
2 (i)What are the foundational principles of "computation" from a Vedic Unit II
perspective? & III
(ii)In Vedic philosophy, "Brahman" represents an underlying, universal truth.
How might context-free grammars (CFG) represent the underlying structure of
languages, transcending surface-level variations?
(iii)The Vedic concept of "Chitta" (mind) can store infinite possibilities. How
does the stack in a pushdown automaton (PDA) symbolize the mind's capacity
to process and store infinite possibilities within finite constraints?
3 (i)Can Vedic mathematical sutras lead to optimal algorithms for complex Unit
computations? IV
(ii)How does the concept of undecidability in Turing machines challenge the
Vedic understanding of "Maya" (illusion), where some truths may forever
remain beyond our grasp?
5
4 Could Vedic concepts of infinity and cyclic time inform complexity theory? Unit V
