AKTU Theory of Automata and Formal Languages · Important Questions 2026Source: ryzenstudy.com PYQs
BCS402 Theory of Automata and Formal Languages Important Questions 2026 (AKTU)
Repeat analysis + most-asked questions, unit-wise
What we did: built from all 5 AKTU Theory of Automata and Formal Languages papers (2021-22–2025-26): 115 questions grouped into 69 distinct questions, 31 of which were asked in more than one paper.
- of marks were repeat questions
- 56%
- of marks were repeat questions
- questions asked in 2+ papers
- 31
- questions asked in 2+ papers
- papers analysed (2021-22–2025-26)
- 5
- papers analysed (2021-22–2025-26)
- units, mapped to current syllabus
- 5
- units, mapped to current syllabus
How much of the paper repeats?
- Repeats are real: when we checked each newer BCS402 paper against the papers before it, on average 56% of its marks were questions already asked in an earlier paper.
- 2023-24 paper: 56% of marks were repeats (8 of 12 repeated questions were in our top list).
- 2024-25 paper: 63% of marks were repeats (5 of 13 repeated questions were in our top list).
- 2025-26 paper: 51% of marks were repeats (4 of 11 repeated questions were in our top list).
- Topic weightage is a guide, not a guarantee: our Tier 1 + Tier 2 topics covered 61% of the next paper's marks — picking the same number of topics at random would have covered about 52%.
Across 10 subjects and 23 papers we tested, 43% of marks repeated earlier questions on average.
1.Unit-wise most-asked questions
Ranked by how many papers asked them, then by how recently. Click a paper to open it.
Unit 1: Basic Concepts and Automata Theory
20% of past marks| Question | Asked |
|---|---|
| Express the minimum state automaton equivalent to the DFA described in the figure below. (see original paper) | Asked 4× |
| Define Deterministic Finite Automata (DFA). | Asked 3× |
| Design a DFA to accept all strings with abb as a substring over alphabet {a,b}. | Asked 2× |
| Construct a DFA corresponding to the following NFA. (see original paper) | Asked 2× |
Unit 2: Regular Expressions and Languages
23% of past marks| Question | Asked |
|---|---|
| Construct the regular expression for the given DFA using Arden's theorem. (see original paper) | Asked 4× |
| Using the pumping lemma, show that L = {a^n b^2n | n >= 1} is not a regular language. | Asked 3× |
| Write the regular expression for the languages: i) Accepting all strings containing any number of 0's and 1's over Σ = {0, 1}. ii) Accepting all strings starting with 10101 over alphabet {0, 1}. | Asked 3× |
| Discuss closure properties (i.e. union, concatenation, complement, intersection and difference) of regular language. | Asked 3× |
Unit 3: Regular and Non-Regular Grammars
22% of past marks| Question | Asked |
|---|---|
| Prove using derivation trees whether the grammar S -> aSb | ε is ambiguous or not. Explain ambiguity. | Asked 3× |
| Convert the following CFG into Chomsky Normal Form (CNF): S -> aSB | ε. | Asked 3× |
| What is ambiguity in a CFG? Construct a CFG for the language L = {a^n b^n | n >= 0}. | Asked 2× |
| Let G be the grammar (productions missing). Determine the leftmost derivation for the string 00110101. (see original paper) | Asked 2× |
Unit 4:
16% of past marks| Question | Asked |
|---|---|
| Why are NPDAs considered more powerful than DPDAs? Provide an example of a language accepted by NPDA but not by DPDA. | Asked 2× |
| Design a Two Stack Pushdown Automaton for the given language. (see original paper) | Asked 2× |
| Design a PDA to accept palindromes over {a, b}. | Asked 2× |
| Construct a PDA equivalent to the following CFG G = ({S, A}, {0,1}, P, S) where P is defined by (productions missing). (see original paper) | Asked 2× |
Unit 5:
19% of past marks| Question | Asked |
|---|---|
| Define the Post Correspondence Problem (PCP). Why is it considered undecidable? | Asked 2× |
| What is a Universal Turing Machine (UTM)? How does it simulate other Turing Machines? | Asked 2× |
| What is a Linear Bounded Automaton (LBA)? | Asked 2× |
| Design a Turing Machine to compute the function f(n) = n + 1 where n is a unary number (e.g., n=3 -> "111"). | Asked 2× |
2.Topic weightage: which topics carry the marks
Blue = Tier 1 + Tier 2 (topics that carried ~80% of past marks). Grey = the rest. It shows where marks have gone, not a promise of what comes next.
DFA definition and design · U1
6.4% (cum 6%)
Pumping lemma for regular languages · U2
6.3% (cum 13%)
Arden's theorem · U2
5.9% (cum 19%)
NFA and NFA-DFA equivalence · U1
5.9% (cum 25%)
Closure properties of regular languages · U2
5.3% (cum 30%)
Ambiguity in grammars · U3
5.2% (cum 35%)
Designing PDAs · U4
4.7% (cum 40%)
CFG to PDA and PDA to CFG · U4
4.3% (cum 44%)
DFA minimization · U1
4.1% (cum 48%)
Regular expressions · U2
4% (cum 52%)
Modifications of Turing machine · U5
3.9% (cum 56%)
Designing Turing machines · U5
3.6% (cum 60%)
Chomsky Normal Form · U3
3.3% (cum 63%)
CFG definition and derivations · U3
3.2% (cum 66%)
Two stack PDA · U4
3.1% (cum 69%)
Halting problem and PCP · U5
3.1% (cum 72%)
Regular grammars · U3
2.8% (cum 75%)
Simplification of CFG · U3
2.8% (cum 78%)
Church's thesis, recursive and RE languages · U5
2.5% (cum 80%)
Designing CFGs · U3
2.4% (cum 83%)
DPDA and DCFL · U4
2.2% (cum 85%)
TM as computer of integer functions · U5
2.2% (cum 87%)
Universal Turing machine · U5
2% (cum 89%)
Chomsky hierarchy · U3
1.6% (cum 91%)
NFA with epsilon moves · U1
1.4% (cum 92%)
NPDA definition and acceptance · U4
1.4% (cum 94%)
Moore and Mealy machines · U1
1% (cum 95%)
Greibach Normal Form · U3
1% (cum 96%)
Linear bounded automata · U5
1% (cum 97%)
Alphabet, strings, languages · U1
1% (cum 98%)
Kleene theorem and transition graph · U2
0.8% (cum 98%)
Pigeonhole principle · U2
0.6% (cum 99%)
Pumping lemma for CFL · U4
0.4% (cum 99%)
Basic Turing machine model · U5
0.4% (cum 100%)
| Topic | Papers | Share |
|---|---|---|
| DFA definition and design · Unit 1 · Tier 1 | 4/5 | 6.4% |
| Pumping lemma for regular languages · Unit 2 · Tier 1 | 5/5 | 6.3% |
| Arden's theorem · Unit 2 · Tier 1 | 4/5 | 5.9% |
| NFA and NFA-DFA equivalence · Unit 1 · Tier 1 | 4/5 | 5.9% |
| Closure properties of regular languages · Unit 2 · Tier 1 | 3/5 | 5.3% |
| Ambiguity in grammars · Unit 3 · Tier 1 | 4/5 | 5.2% |
| Designing PDAs · Unit 4 · Tier 1 | 3/5 | 4.7% |
| CFG to PDA and PDA to CFG · Unit 4 · Tier 1 | 3/5 | 4.3% |
| DFA minimization · Unit 1 · Tier 1 | 4/5 | 4.1% |
| Regular expressions · Unit 2 · Tier 1 | 4/5 | 4% |
| Modifications of Turing machine · Unit 5 · Tier 2 | 2/5 | 3.9% |
| Designing Turing machines · Unit 5 · Tier 2 | 4/5 | 3.6% |
| Chomsky Normal Form · Unit 3 · Tier 2 | 3/5 | 3.3% |
| CFG definition and derivations · Unit 3 · Tier 2 | 3/5 | 3.2% |
| Two stack PDA · Unit 4 · Tier 2 | 4/5 | 3.1% |
| Halting problem and PCP · Unit 5 · Tier 2 | 4/5 | 3.1% |
| Regular grammars · Unit 3 · Tier 2 | 3/5 | 2.8% |
| Simplification of CFG · Unit 3 · Tier 2 | 2/5 | 2.8% |
| Church's thesis, recursive and RE languages · Unit 5 · Tier 2 | 2/5 | 2.5% |
| Designing CFGs · Unit 3 · Tier 3 | 4/5 | 2.4% |
| DPDA and DCFL · Unit 4 · Tier 3 | 2/5 | 2.2% |
| TM as computer of integer functions · Unit 5 · Tier 3 | 2/5 | 2.2% |
| Universal Turing machine · Unit 5 · Tier 3 | 2/5 | 2% |
| Chomsky hierarchy · Unit 3 · Tier 3 | 2/5 | 1.6% |
| NFA with epsilon moves · Unit 1 · Tier 3 | 2/5 | 1.4% |
| NPDA definition and acceptance · Unit 4 · Tier 3 | 3/5 | 1.4% |
| Moore and Mealy machines · Unit 1 · Tier 3 | 1/5 | 1% |
| Greibach Normal Form · Unit 3 · Tier 3 | 1/5 | 1% |
| Linear bounded automata · Unit 5 · Tier 3 | 2/5 | 1% |
| Alphabet, strings, languages · Unit 1 · Tier 3 | 2/5 | 1% |
| Kleene theorem and transition graph · Unit 2 · Tier 3 | 2/5 | 0.8% |
| Pigeonhole principle · Unit 2 · Tier 3 | 1/5 | 0.6% |
| Pumping lemma for CFL · Unit 4 · Tier 3 | 1/5 | 0.4% |
| Basic Turing machine model · Unit 5 · Tier 3 | 1/5 | 0.4% |
3.Paper pattern (2025-26)
| Section | Questions | Rule |
|---|---|---|
| A | 7 × 2 marks | Attempt all |
| B | 5 × 7 marks | Attempt any 3 |
| C | 10 × 7 marks | Attempt any 1 |
4.In the syllabus, never asked yet
Low priority, but read them once — a new paper can always start here.
- Decidability and decision properties · U2
- Closure and decision problems of CFL · U4
5.Study order
- 1DFA definition and design (Unit 1, Tier 1)
- 2Pumping lemma for regular languages (Unit 2, Tier 1)
- 3Arden's theorem (Unit 2, Tier 1)
- 4NFA and NFA-DFA equivalence (Unit 1, Tier 1)
- 5Closure properties of regular languages (Unit 2, Tier 1)
- 6Ambiguity in grammars (Unit 3, Tier 1)
- 7Designing PDAs (Unit 4, Tier 1)
- 8CFG to PDA and PDA to CFG (Unit 4, Tier 1)
- 9DFA minimization (Unit 1, Tier 1)
- 10Regular expressions (Unit 2, Tier 1)
- 11Modifications of Turing machine (Unit 5, Tier 2)
- 12Designing Turing machines (Unit 5, Tier 2)
- 13Chomsky Normal Form (Unit 3, Tier 2)
- 14CFG definition and derivations (Unit 3, Tier 2)
- 15Two stack PDA (Unit 4, Tier 2)
- 16Halting problem and PCP (Unit 5, Tier 2)
- 17Regular grammars (Unit 3, Tier 2)
- 18Simplification of CFG (Unit 3, Tier 2)
- 19Church's thesis, recursive and RE languages (Unit 5, Tier 2)
FAQ
Which units of BCS402 carry the most marks?
Unit 2 (Regular Expressions and Languages, 23% of past marks) and Unit 3 (Regular and Non-Regular Grammars, 22% of past marks).
Do AKTU Theory of Automata and Formal Languages questions repeat?
Yes. On average 56% of the marks in each newer BCS402 paper came from questions already asked in an earlier paper, and 31 questions have appeared in more than one paper.
How is this list made?
Every question from the 5 papers (2021-22–2025-26) was mapped to the current AKTU syllabus and grouped with the same question from other years. Questions are ranked by how many papers they appeared in, then by how recently.
Study this subject
Note: this is based on past AKTU papers, not a guarantee. Questions are mapped to the current syllabus; topics that are no longer in the syllabus are left out.