Theory of Automata and Formal Languages Unit 1 – Basic Concepts and Automata Theory: AKTU previous year questions
31 AKTU questions from Unit 1 (Basic Concepts and Automata Theory) asked in 2018–2025, tagged by marks, year and topic. In short: about 28 marks of every paper come from this unit; the most asked topic is Non Deterministic Finite Automaton (10 times); 20 questions came back in a later year. The latest ones are listed below; on the page you can filter them by 2-mark or long questions, topic and repeats.
Unit 1 previous year questions
- 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)
- Give the mathematical definition of DFA. Differentiate between NFA and DFA. (2 marks, 2024, Deterministic Finite Automaton)
- Construct Deterministic Finite Automata (DFA) to accept string that always ends with 101 over alphabet Σ ={0,1} (2 marks, 2024, Deterministic Finite Automaton)
- Construct a Finite automata (DFA) which accepts all binary numbers whose decimal equivalent is divisible by 4 over Σ = {0, 1}. (7 marks, 2024, Deterministic Finite Automaton)
- Construct a DFA corresponding to the following NFA with ε moves: (7 marks, 2024, Non Deterministic Finite Automaton)
- Express in the minimum state automata equivalent to DFA described in below figure: (7 marks, 2024, Minimization of Finite Automata)
- What do you mean by ε-Closure in FA? (2 marks, 2023, Non Deterministic Finite Automaton)
- Construct a DFA for ternary number divisible by 4. (10 marks, 2023, Deterministic Finite Automaton)
Most asked Unit 1 topics
- Non Deterministic Finite Automaton – asked 10 times
- Deterministic Finite Automaton – asked 8 times
- Minimization of Finite Automata – asked 8 times
Unit 1 question pattern
- 2-mark questions: 13 asked in 2018–2025
- 7-mark questions: 12 asked in 2018–2025
- 10-mark questions: 6 asked in 2018–2025
- About 28 marks from Unit 1 in every paper
- 20 questions were asked again in a later year
Unit 1 questions year by year
- 2025: 5 Unit 1 questions asked (25 marks across that year's papers)
- 2024: 5 Unit 1 questions asked (25 marks across that year's papers)
- 2023: 4 Unit 1 questions asked (32 marks across that year's papers)
- 2022: 5 Unit 1 questions asked (34 marks across that year's papers)
- 2019: 6 Unit 1 questions asked (27 marks across that year's papers)
- 2018: 6 Unit 1 questions asked (27 marks across that year's papers)