Theory of Automata and Formal Languages (BCS402) AKTU previous year questions 2018–2025
Every Theory of Automata and Formal Languages question from 6 AKTU papers, tagged by unit, topic and marks. A few recent questions from each unit are listed below; open the page to filter by unit, topic or mark type.
Unit 1: Basic Concepts and Automata Theory – AKTU PYQs
- Define the term "Alphabet" in the context of automata theory. (2 marks, 2025, Introduction to Theory of Computation)
- Differentiate between DFA and NFA. (2 marks, 2025, Non Deterministic Finite Automaton)
- Prove that for every NFA, there exists an equivalent DFA. Show construction using subset method for the given NFA: States = {q0, q1}, Input = {0,1}, Start = q0, Final = {q1}, Transitions: δ(q0, 0) = {q0, q1}, δ(q0, 1) = {q0}, δ(q1, 1) = {q1} (7 marks, 2025, Non Deterministic Finite Automaton)
- Construct a DFA corresponding to the following NFA: (7 marks, 2025, Non Deterministic Finite Automaton)
- Express in the minimum state automata equivalent to DFA described in below figure: (7 marks, 2025, Minimization of Finite Automata)
Unit 2: Regular Expressions and Languages – AKTU PYQs
- Write the regular expression for the language containing strings over {0,1} ending with 01. (2 marks, 2025, Regular Expressions)
- 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 (7 marks, 2025, Arden's Theorem)
- Using Pumping Lemma, show that the language L = {aⁿbⁿcⁿ | n ≥ 0} is not regular. (7 marks, 2025, Pumping Lemma for Regular Languages)
- Prove that (a+b)*a(a+b)* is a regular language using Arden's Theorem. (7 marks, 2025, Arden's Theorem)
- Give regular expressions that represent the language (L), which has all binary strings having two consecutive 0s and two consecutive 1s over the alphabet Σ = {0, 1}. (2 marks, 2024, Regular Expressions)
Unit 3: Regular and Non-Regular Grammars – AKTU PYQs
- What is the ambiguity in Context-Free Grammars (CFGs)? (2 marks, 2025, Context Free Grammar)
- Construct a CFG for the language L = {aⁿbⁿ | n ≥ 0}. (2 marks, 2025, Context Free Grammar)
- Find whether the following grammar is ambiguous or not: S → S*S | S+S | a (2 marks, 2025, Context Free Grammar)
- Convert the following regular grammar to a Finite Automaton: S → aA | bB, A → aS | a, B → bS | b (7 marks, 2025, FA and Regular Grammar Conversion)
- Convert the following CFG into Chomsky Normal Form (CNF): S → aSB | ε, B → b (7 marks, 2025, Normal Forms of CFG)
Unit 4: Push Down Automata and Properties of Context Free Languages – AKTU PYQs
- Design a PDA that accepts the language L = {ww^R | w ∈ {a, b}*}. (7 marks, 2025, Nondeterministic Pushdown Automata)
- Design a PDA to accept palindromes over {a, b}. (7 marks, 2025, Nondeterministic Pushdown Automata)
- Explain the concept of two stack PDA. Give an example of a language that is accepted by two stack PDA but not accepted by normal one stack PDA. (2 marks, 2024, Two Stack Pushdown Automata)
- Differentiate between DPDA and NPDA. Construct a PDA that accepts language L = {aⁿbⁿ | n ≥ 1}. (7 marks, 2024, Deterministic Pushdown Automata)
- Construct PDA equivalent to the following CFG G = ({S, A}, {0,1}, P, S} where P is defined by: S → 0S1 | A, A → 1A0 | S | ε (7 marks, 2024, PDA and CFG Interconversion)
Unit 5: Turing Machines and Recursive Function Theory – AKTU PYQs
- Design a Turing Machine to accept the language L = {aⁿbⁿ | n ≥ 1}. (2 marks, 2025, Turing Machine Construction Techniques)
- Design a Turing Machine to compute the function f(n) = n + 1 where n is a unary number (e.g., n=3 → "111"). (7 marks, 2025, Basic Turing Machine Model)
- Explain the concept of Universal Turing Machine. Construct a Turing Machine that computes f(n) = 2n for unary input. (7 marks, 2025, Modifications of Turing Machine)
- Discuss Post's Correspondence Problem (PCP) with an example showing undecidability. (7 marks, 2025, Recursive and RE Languages)
- Explain Multi Tape Turing Machine. (2 marks, 2024, Modifications of Turing Machine)