TAFL PYQ 2024-25 AKTU Question Paper

AKTU · BTECH · Semester 4 · Theory of Automata and Formal Languages · Session 2024-25 · PYQ

AKTU Theory of Automata and Formal Languages previous year question paper 2024-25 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 2024-25

  1. Q1a. Define the term "Alphabet" in the context of automata theory. (2 marks, 2024-25)
  2. Q1b. Differentiate between DFA and NFA. (2 marks, 2024-25)
  3. Q1c. Write the regular expression for the language containing strings over {0,1} ending with 01. (2 marks, 2024-25)
  4. Q1d. What is the ambiguity in Context-Free Grammars (CFGs)? (2 marks, 2024-25)
  5. Q1e. Construct a CFG for the language L = {aⁿbⁿ | n ≥ 0}. (2 marks, 2024-25)
  6. Q1f. Find whether the following grammar is ambiguous or not: S → S*S | S+S | a (2 marks, 2024-25)
  7. Q1g. Design a Turing Machine to accept the language L = {aⁿbⁿ | n ≥ 1}. (2 marks, 2024-25)
  8. Q2a. 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, 2024-25)
  9. Q2b. 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, 2024-25)
  10. Q2c. Convert the following regular grammar to a Finite Automaton: S → aA | bB, A → aS | a, B → bS | b (7 marks, 2024-25)
  11. Q2d. Design a PDA that accepts the language L = {ww^R | w ∈ {a, b}*}. (7 marks, 2024-25)
  12. Q2e. 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, 2024-25)
  13. Q3a. Construct a DFA corresponding to the following NFA: (7 marks, 2024-25)
  14. Q3b. Express in the minimum state automata equivalent to DFA described in below figure: (7 marks, 2024-25)
  15. Q4a. Using Pumping Lemma, show that the language L = {aⁿbⁿcⁿ | n ≥ 0} is not regular. (7 marks, 2024-25)
  16. Q4b. Prove that (a+b)*a(a+b)* is a regular language using Arden's Theorem. (7 marks, 2024-25)
  17. Q5a. Convert the following CFG into Chomsky Normal Form (CNF): S → aSB | ε, B → b (7 marks, 2024-25)
  18. Q5b. Prove using derivation trees whether the grammar: S → aSb | ε is ambiguous or not. Explain ambiguity. (7 marks, 2024-25)
  19. Q6a. Simplify the following CFG: S → AbaC, A → BC, B → b | ε, C → D | ε, D → d (7 marks, 2024-25)
  20. Q6b. Design a PDA to accept palindromes over {a, b}. (7 marks, 2024-25)
  21. Q7a. Explain the concept of Universal Turing Machine. Construct a Turing Machine that computes f(n) = 2n for unary input. (7 marks, 2024-25)
  22. Q7b. Discuss Post's Correspondence Problem (PCP) with an example showing undecidability. (7 marks, 2024-25)

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