TAFL Unit 5 Handwritten Notes AKTU (BCS402)

AKTU · BTECH · Semester 4 · Theory of Automata and Formal Languages · Unit 5 · Handwritten Notes

AKTU Theory of Automata and Formal Languages (BCS402) Unit 5 handwritten notes for B.Tech Semester 4 – Turing Machines and Recursive Function Theory…

A preview is available. Sign in or check access options in the reader for the complete resource.

Unit 5: Turing Machines and Recursive Function Theory – AKTU syllabus topics

Basic Turing Machine Model: Representation of Turing Machines, Language Acceptability of TM
Turing Machine Construction Techniques
Modifications of Turing Machine: Universal Turing Machine, Linear Bounded Automata, TM as Integer Functions Computer
Church's Thesis
Recursive and RE Languages: Halting Problem, Post's Correspondence Problem
Recursive Function Theory

Q7b. Discuss Post's Correspondence Problem (PCP) with an example showing undecidability. (7 marks, 2024-25)
Q7a. Explain the concept of Universal Turing Machine. Construct a Turing Machine that computes f(n) = 2n for unary input. (7 marks, 2024-25)
Q7b. Explain the any two of the following: i. Universal Turing Machine. ii. Post Correspondence Problem. iii. Recursive and recursively Enumerable Languages (7 marks, 2023-24)
Q7a. Design a Turing Machine for the language: L={a^n b^n c^n | n>=1} (10 marks, 2022-23)
Q7b. Write short notes on: (i) Variants of Turing Machine (ii) Post Correspondence problem (iii) Universal Turing Machine (10 marks, 2022-23)
Q1i. Explain Halting Problem of Turing Machine. (2 marks, 2022-23)
Q2e. Write short notes on: i) Church's Thesis ii) Recursive and Recursive Enumerable Language (10 marks, 2022-23)
Q3a. Write short notes on following. i) Turing Machine as Computer of Integer Functions ii) Universal Turing machine (10 marks, 2021-22)
Q5b. Design a Turing Machine for the language L. Where, L={aⁿbⁿcⁿ | n≥1} (10 marks, 2021-22)
Q1g. Design a Turing Machine to accept the language L = {aⁿbⁿ | n ≥ 1}. (2 marks, 2024-25)