Theory of Automata and Formal Languages (BCS402) AKTU predicted paper 2026-27
AI-predicted paper for Theory of Automata and Formal Languages based on 6 past papers (2018, 2019, 2022, 2023, 2024, 2025). NOT an official AKTU paper. Use as a revision tool only.
Paper pattern
- Section A: Attempt all questions. (14 marks)
- Section B: Attempt any THREE questions out of five. (21 marks)
- Section C: Attempt ONE question from each pair (a or b). (35 marks)
Why these questions
- Unit 2 (Regular Expressions and Languages) dominates — 23% avg weightage
- Asked every year: Non Deterministic Finite Automaton, Minimization of Finite Automata
- Due for comeback: Chomsky Hierarchy, Pumping Lemma for CFL
- Low priority (never asked): Recursive Function Theory
- Most repeated topic: Context Free Grammar
Section A – 2-mark questions
- Differentiate between DFA and NFA.
- State Arden's Theorem.
- What is the ambiguity in Context-Free Grammars (CFGs)?
- Draw the graphical representation for PDA.
- Explain Halting Problem of Turing Machine.
- Write a short note on Pumping Lemma for Regular Languages.
- Write a short note on Minimization of Finite Automata.
Section B – sample questions
- Prove using Arden's Theorem the regular expression for the following transition diagram: States: A (start), B (final). Transitions: A --a--> A, A --b--> B, B --a--> B
- Discuss Post's Correspondence Problem (PCP) with an example showing undecidability.
- Using Pumping Lemma, show that the language L = {aⁿbⁿcⁿ | n ≥ 0} is not regular.