TAFL PYQ 2025-26 AKTU Question Paper

AKTU · BTECH · Semester 4 · Theory of Automata and Formal Languages · Session 2025-26 · PYQ

AKTU Theory of Automata and Formal Languages previous year question paper 2025-26 for B.Tech Semester 4. Covers Basic Concepts and Automata Theory, Regular…

Open the interactive reader to study this resource on AcademicArk.

Theory of Automata and Formal Languages AKTU syllabus

  1. Unit 1: Basic Concepts and Automata Theory
  2. Unit 2: Regular Expressions and Languages
  3. Unit 3: Regular and Non-Regular Grammars
  4. Unit 4: Push Down Automata and Properties of Context Free Languages
  5. Unit 5: Turing Machines and Recursive Function Theory

Questions in Theory of Automata and Formal Languages AKTU PYQ 2025-26

  1. Q1a. Define Deterministic Finite Automata (DFA). (2 marks, 2025-26)
  2. Q1b. Design a DFA to accept all strings with abb as substring over alphabet {a,b}. (2 marks, 2025-26)
  3. Q1c. Find the shortest string not in the language of the regular expression a^*(ba)^*. (2 marks, 2025-26)
  4. Q1d. State the Pigeonhole Principle. (2 marks, 2025-26)
  5. Q1e. Explain the difference between non-generating and unreachable symbols. (2 marks, 2025-26)
  6. Q1f. Define acceptance by final state and acceptance by empty stack in a PDA. (2 marks, 2025-26)
  7. Q1g. What is a Linear Bounded Automaton (LBA). (2 marks, 2025-26)
  8. Q2a. Design a DFA which accepts set of strings such that every string containing 00 as substring but not 000 as a substring. (7 marks, 2025-26)
  9. Q2b. Using the pumping lemma, show that L={a^nb^{2n} | n≥1} is not regular language. (7 marks, 2025-26)
  10. Q2c. Remove ε-productions from the given grammar: S→ AB | BC, A→ aA | ε, B→ bB | ε, C→ c (7 marks, 2025-26)
  11. Q2d. Construct PDA that accepts L={a^nb^{2n} | n≥1}. (7 marks, 2025-26)
  12. Q2e. Define the Post Correspondence Problem (PCP). Why is it considered undecidable? (7 marks, 2025-26)
  13. Q3a. Define Non-Deterministic Finite Automata. Design a NFA to accepts strings over {0,1} containing the substring 1101. (7 marks, 2025-26)
  14. Q3b. Define the Moore machine. Design a Moore machine to generate 1’s complement of given binary numbers. (7 marks, 2025-26)
  15. Q4a. Write the regular expression for the languages: (i) Accepting all the string containing any number of 0's and 1's over the set Σ={0,1}. (ii) Accepting all the string starting with 10101 over alphabet {0,1}. (7 marks, 2025-26)
  16. Q4b. Construct regular expression for given DFA using Arden’s theorem. (7 marks, 2025-26)
  17. Q5a. Define Greibach Normal Form (GNF). Convert the following CFG into GNF: S→ CD, C→ DS | d, D→ SC | c (7 marks, 2025-26)
  18. Q5b. What is ambiguity in a CFG? Construct a CFG for the language L={a^nb^n | n≥0}. (7 marks, 2025-26)
  19. Q6a. Design Two Stack Pushdown Automata for the given language: L={a^nb^nc^n | n≥1}. (7 marks, 2025-26)
  20. Q6b. Why are NPDAs considered more powerful than DPDAs? Provide an example of a language accepted by NPDA but not by DPDA. (7 marks, 2025-26)
  21. Q7a. What is a Universal Turing Machine (UTM)? How does it simulate other Turing Machines? (7 marks, 2025-26)
  22. Q7b. Design a Turingmachine that accepts L={0^{2n}/n≥0}. (7 marks, 2025-26)

AKTU paper codes: BCS402, KCS402, RCS403

Theory of Automata and Formal Languages previous year papers

More Theory of Automata and Formal Languages resources

Browse all notes · Semester 4 notes · Theory of Automata (TAFL) notes