Question 1: Find an explicit Turing machine accepting the language L = {anbncn|n≥2} . Explain briefly why it accepts L.
Question 2: Suppose T is a TM accepting the language L. Describe how you would modify T to obtain another TM accepting L that never halts in the reject state hr.
Question 3: Draw the Insert(σ) TM, which changes the tape contents from yz?σ to yσz, where y ∈ (Σ ∪ {?})∗, σ ∈ Σ ∪ {?}, and z ∈ Σ∗ with Σ = {a, b}.
Question 4: Let T be a TM accepting language L. Show that if there is an integer n so that no matter what the input string is, T never moves its tape head to the right of the nth tape square, then L is regular.
Question 5: Find an unrestricted grammar that generates the following language:
{anxbn | n ≥ 1, x ∈ {a, b}∗ , |x| = n} .
Question 6: Suppose that L is recursively enumerable but not recursive. Show that if T is a TM accepting L, then the language L1 consisting of strings for which T runs forever is not recursively enumerable.=
Question 7: Determine whether the following decision problems are decidable or undecidable:
(a) Given a TM T , does it ever reach a state other than its initial state if it starts with a blank tape?
(b) Given a TM T , does T eventually enter every one of its nonhalting states if it begins with a blank tape?
We offer the finest Turing Machine Assignment Help services at the most viable prices that no other online service provider organizations can provide.
Tags: Turing Machine Assignment Help, Turing Machine Homework Help, Turing Machine Coursework, Turing Machine Solved Assignments
Attachment:- Turing machine-Theory of Computation.rar