✅ UNIT 1 – Basic Concepts and Finite Automata

Syllabus Topics:
 Automata, Computability, Complexity
 Alphabet, Symbol, String, Formal Languages
 DFA, NFA, ε-NFA
 Moore and Mealy Machines
 Minimization of FA
Mapped Questions:
1. Define DFA, NFA & Language.
2. Give applications of Finite Automata.
3. Explain the ground rules of finite automata.
4. Convert NFA to DFA using subset construction
method.
5. Convert given DFA to Regular Expression.
6. Convert NFA to DFA (given transition table).
7. Explain extended transition function of NFA with
example.
8. Design DFA for:
o Exactly one ‘a’
o Even number of a’s and b’s
o Strings starting with ab
o Strings ending with 011
o Binary numbers divisible by 3
o Substring “aa”
 o Strings starting with 0, odd number of 1’s,
ending with 2
9. Minimize a given DFA.
10. DFA for intersection of two regular languages.
11. DFA for closure of states.
12. Moore & Mealy Machine conversion.

✅ UNIT 2 – Regular Expressions and Languages

Syllabus Topics:
 Regular Expressions
 Kleene’s Theorem, Arden’s Theorem
 Closure Properties
 Pumping Lemma
 Regular vs Non-Regular Languages
 Decision Properties
Mapped Questions:
1. Write regular expressions for:
o {aⁿbᵐ | m, n are even}
o {aⁿbᵐ | m≥2, n≥2}
2. Define Regular Expression.
3. Applications of Regular Expressions.
4. Convert DFA to Regular Expression.
5. Show the language {aibj | i≠j} is not regular.
6. Prove with Pumping Lemma:
 o Palindromes are not regular.
o L = {1ⁿ | n is prime} is not regular.
o {aⁿbᵐcᵐdⁿ}, {aⁿ | n is a perfect square}, {ww}
not regular.
7. Write closure properties of regular languages.
8. Derive regular expression using Arden’s Theorem.
9. Use Kleene’s Theorem for construction.

✅ UNIT 3 – Grammars (CFG) and Context-Free

Languages
Syllabus Topics:
 Context-Free Grammar (CFG)
 Derivation Trees, Ambiguity
 Regular Grammar
 Simplification, CNF & GNF
 Chomsky Hierarchy
Mapped Questions:
1. Define grammar and explain Chomsky Hierarchy.
2. Explain ambiguous grammar with example.
3. Grammar for:
o {0ⁿ1ⁿ | n ≥ 1}
o {aⁱbʲcᵏ | i≠j or j≠k}
o {wwᴿ | w ∈ {a,b}*}
o {w | nₐ(w) > nᵦ(w)}
 o {0ᵐ1ᵐ2ⁿ | m ≥ 1, n ≥ 0}
4. Derivations (leftmost, rightmost) for strings like
00101, 1001.
5. Generate CFG for RE: 01(0+1)
6. Explain CFG simplification: CNF, GNF, removing ε-
productions, useless symbols.
7. Explain decision properties for regular/CFG
languages.

✅ UNIT 4 – Pushdown Automata and CFL

Properties
Syllabus Topics:
 PDA (NPDA & DPDA)
 Conversion between PDA & CFG
 Pumping Lemma for CFL
 Closure and Decision Properties
Mapped Questions:
1. Define PDA. Construct PDA for:
o {aⁿbⁿ | n ≥ 1}
o {wcwᴿ}
o Balanced parentheses
o {aⁱbʲcᵢ+ⱼ}
o {aᵢbⱼ | i > j}
o If-Else structure of C
o Equal number of a’s and b’s
 2. Convert CFG to PDA and vice versa.
3. Design PDA accepting by empty stack and by final
state.
4. Show ambiguous grammar for aab.
5. PDA design:
o No prefix has more 1’s than 0’s
o Number of 1’s < Number of 0’s
6. Eliminate nullable/epsilon productions from CFG.
7. Eliminate unreachable/useless symbols.
8. Pumping Lemma for CFL: Prove non-CFLs like:
o {aᵢbᵢcᵢ | i ≥ 1}
o {ww | w ∈ {0,1}*}
o Prime number of symbols

✅ UNIT 5 – Turing Machines and Undecidability

Syllabus Topics:
 Turing Machine (TM): Basic Model, Variants,
Universal TM
 Recursive & Recursively Enumerable Languages
 Church-Turing Thesis, Halting Problem
 Post’s Correspondence Problem (PCP)
 Decidability, Undecidability
Mapped Questions:
1. Design Turing Machines for:
 o Palindromes
o {aⁿb²ⁿ}
o {0ⁿ1ⁿ2ⁿ}
o Number of 0s not twice the number of 1s
2. Explain Halting Problem.
3. Define and explain:
o Undecidability
o Decidability
4. Post’s Correspondence Problem (PCP)
5. Show that some problems are not solvable by
computers.
6. Recursive language properties.
✅ UNIT 1 – Finite Automata (DFA, NFA, Mealy,
Moore, Minimization)
Topics:
 DFA, NFA, ε-NFA
 DFA minimization
 Mealy/Moore machines
 DFA/NFA construction
Past Questions:
 Design DFA that accepts binary numbers divisible
by 4/5. (2023-24, 2017-18)
 DFA for strings ending with 101. (2023-24, 2018-
19)
 DFA from NFA with ε-moves. (2023-24, 2016-17)
 DFA for even number of a’s and b’s. (2016-17)
 DFA for strings where third symbol from right is 'a'.
(2021-22)
 Construct minimum-state DFA. (2017-18, 2023-24)
 Compare NFA vs DFA; define ε-closure. (2023-24,
2022-23)
 Convert FA to left-linear grammar. (2016-17)
 Define Mealy and Moore machine and convert.
(2017-18)

✅ UNIT 2 – Regular Languages, Regular

Expressions, Closure Properties
Topics:
  Regular Expressions
 Arden’s Theorem, Kleene’s Theorem
 Pumping Lemma
 Closure Properties
 Regular vs Non-Regular
Past Questions:
 State and prove Pumping Lemma; apply on L = {aᵖ
| p prime}. (2016-17, 2023-24, 2022-23)
 Use Arden’s Theorem to derive RE from DFA.
(2023-24)
 Write regular expressions for strings with specific
patterns. (2017-18, 2023-24)
 Prove closure properties: union, intersection, etc.
(2021-22, 2022-23, 2023-24)
 Language accepted by given FA/RE. (2018-19,
2022-23)
 Define and explain Kleene’s Theorem. (2021-22,
2022-23)

✅ UNIT 3 – Context-Free Grammars, Chomsky

Normal Form, Ambiguity
Topics:
 CFGs, CNF, GNF
 Derivations, Parse Trees
 Ambiguity
 Chomsky Hierarchy
Past Questions:
 Convert CFG to CNF. (2017-18, 2022-23, 2023-24)
 Determine ambiguity in grammar. (2017-18, 2022-
23, 2021-22)
 Parse tree and derivation of string. (2016-17, 2021-
22)
 Derive CFG for languages like (a + b)*, aᵐbⁿ where
m ≠ n. (2023-24, 2022-23)
 Chomsky hierarchy explanation. (2022-23, 2021-
22)
 Construct CFG from PDA. (2023-24)

✅ UNIT 4 – Pushdown Automata and Context-Free

Languages
Topics:
 PDA construction (NPDA, DPDA)
 PDA from CFG and vice versa
 Properties of CFLs (pumping lemma, closure)
 Two-stack PDA
Past Questions:
 Construct PDA for:
o Balanced parentheses (2016-17)
o L = {wcwᴿ} (2022-23, 2017-18)
o L = aⁿbⁿcⁿ (2022-23, 2023-24)
o L = aⁿbⁿ (2017-18, 2018-19)
  Convert CFG to PDA (2023-24)
 Difference between DPDA and NPDA (2017-18,
2023-24)
 Two-stack PDA explanation (2023-24, 2021-22)

✅ UNIT 5 – Turing Machines, Recursive Languages,

Decidability
Topics:
 TM construction and variants
 Recursive & Recursively Enumerable languages
 Universal TM
 PCP, Halting Problem
 Decidability
Past Questions:
 Construct TM for:
o L = {aⁿbⁿcⁿ} (2023-24, 2021-22, 2018-19)
o L = {odd number of α’s} (2016-17)
 Explain Universal TM, Multi-tape TM. (2023-24,
2021-22)
 Post Correspondence Problem (2023-24, 2017-18)
 Recursive vs Recursively Enumerable languages
(2023-24, 2022-23)
 Halting Problem explanation (2022-23, 2016-17,
2021-22)
🔍 Summary by Frequency
Uni
High-Frequency Topics
t
1 DFA construction, minimization, ε-NFA to DFA
Regular expressions, Arden’s Theorem, Pumping
2
Lemma
CFG to CNF, Ambiguity detection, Chomsky
3
Hierarchy
4 PDA design, DPDA vs NPDA, PDA to/from CFG
TM construction, Halting Problem, PCP,
5
Recursive/RE sets