Home › AKTU PYQ › Theory of Automata and Formal Languages › Important Questions › Unit 1

Theory of Automata and Formal Languages Unit 1 – Basic Concepts and Automata Theory: important questions for AKTU

Unit 1 (Basic Concepts and Automata Theory) questions that AKTU repeats most often. This unit carries about 28 marks per paper. Start with the repeated questions, then the most asked topics.

Most repeated Unit 1 questions

  • Express in the minimum state automata equivalent to DFA described in below figure: (7 marks, 2025, Minimization of Finite Automata) – also asked in 2018, 2019, 2022, 2023, 2024
  • Construct a DFA corresponding to the following NFA: (7 marks, 2025, Non Deterministic Finite Automaton) – also asked in 2022, 2023, 2024
  • 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) – also asked in 2018, 2019, 2023

Most important Unit 1 topic

  • Non Deterministic Finite Automaton (Unit 1: Basic Concepts and Automata Theory) – asked 10 times in 2018, 2019, 2022, 2023, 2024, 2025

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

More 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)
  • 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)

Unit 1 syllabus topics

  • Introduction to Theory of Computation
  • Deterministic Finite Automaton
  • Non Deterministic Finite Automaton
  • Finite Automata with Output
  • Minimization of Finite Automata