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

Theory of Automata and Formal Languages Unit 5 – Turing Machines and Recursive Function Theory: important questions for AKTU

Unit 5 (Turing Machines and Recursive Function Theory) questions that AKTU repeats most often. This unit carries about 26 marks per paper. Start with the repeated questions, then the most asked topics.

Most repeated Unit 5 questions

  • Discuss Post's Correspondence Problem (PCP) with an example showing undecidability. (7 marks, 2025, Recursive and RE Languages) – also asked in 2018, 2019, 2022, 2023, 2024
  • 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) – also asked in 2018, 2019, 2022, 2023
  • Explain the any two of the following: i. Universal Turing Machine. ii. Post Correspondence Problem. iii. Recursive and recursively Enumerable Languages (7 marks, 2024, Recursive and RE Languages) – also asked in 2018, 2019, 2022, 2023

Most important Unit 5 topic

  • Recursive and RE Languages (Unit 5: Turing Machines and Recursive Function Theory) – asked 8 times in 2018, 2019, 2022, 2023, 2024, 2025

Most asked Unit 5 topics

  • Recursive and RE Languages – asked 8 times
  • Turing Machine Construction Techniques – asked 7 times
  • Modifications of Turing Machine – asked 5 times

More Unit 5 previous year questions

  • 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 Multi Tape Turing Machine. (2 marks, 2024, Modifications of Turing Machine)
  • Differentiate between Deterministic Turing machine and Non-Deterministic Turing machine. Design a Turing machine for the language L={ww | w ε (a + b)*}. (7 marks, 2024, Turing Machine Construction Techniques)
  • Construct Turing Machine that accepts language L={a²ⁿbⁿ | n>=1}. Also show the instantaneous description for the string w = aaaabb. (7 marks, 2024, Turing Machine Construction Techniques)

Unit 5 syllabus topics

  • Basic Turing Machine Model
  • Turing Machine Construction Techniques
  • Modifications of Turing Machine
  • Church's Thesis
  • Recursive and RE Languages
  • Recursive Function Theory