Theory of Automata and Formal Languages Unit 5 – Turing Machines and Recursive Function Theory: AKTU previous year questions
25 AKTU questions from Unit 5 (Turing Machines and Recursive Function Theory) asked in 2018–2025, tagged by marks, year and topic. In short: about 26 marks of every paper come from this unit; the most asked topic is Recursive and RE Languages (8 times); 14 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 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 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)
- Discuss Post's Correspondence Problem (PCP) with an example showing undecidability. (7 marks, 2025, Recursive and RE Languages)
- 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)
- 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)
- Explain Halting Problem of Turing Machine. (2 marks, 2023, Recursive and RE Languages)
- Explain Linear bounded Automata. (2 marks, 2023, Modifications of Turing Machine)
- Write short notes on: i) Church's Thesis ii) Recursive and Recursive Enumerable Language (10 marks, 2023, Church's Thesis)
- Design a Turing Machine for the language: L={a^n b^n c^n | n>=1} (10 marks, 2023, Turing Machine Construction Techniques)
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
Unit 5 question pattern
- 2-mark questions: 7 asked in 2018–2025
- 7-mark questions: 12 asked in 2018–2025
- 10-mark questions: 6 asked in 2018–2025
- About 26 marks from Unit 5 in every paper
- 14 questions were asked again in a later year
Unit 5 questions year by year
- 2025: 4 Unit 5 questions asked (23 marks across that year's papers)
- 2024: 4 Unit 5 questions asked (23 marks across that year's papers)
- 2023: 5 Unit 5 questions asked (34 marks across that year's papers)
- 2022: 5 Unit 5 questions asked (34 marks across that year's papers)
- 2019: 4 Unit 5 questions asked (23 marks across that year's papers)
- 2018: 3 Unit 5 questions asked (21 marks across that year's papers)