Find an explicit turing machine accepting the language

Assignment Help Theory of Computation

Reference no: EM132500616

APM 3430 Theory of Computation - Oakland University

Question 1. Find an explicit Turing machine accepting the language L = {aⁿbⁿcⁿ|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 h_r.

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:

{aⁿxbⁿ | 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?

Attachment:- Theory of Computation.rar

Reference no: EM132500616

Questions Cloud

How your memo applied the concepts from the background : Conclude your paper with a discussion of how your memo applied the concepts from the background materials. Be specific as to what sources you used.

Conduct research prospectus on the effects of women staying : Conduct research prospectus on the effects of women staying in an abusive relationships, with focus on societal factors such as hardship, parenting

What do you think led to charles kochs victory in the battle : Ultimately what do you think led to Charles Koch's victory in this battle, and what do you think are the most important lessons on organizational power.

Calculate actual number of direct labour hours incurred : Calculate Actual number of direct labour hours incurred, Labour efficiency variance, Materials quantity variance, Fixed overhead budget variance

Find an explicit turing machine accepting the language : Find an explicit Turing machine accepting the language and Find an unrestricted grammar that generates

Calculate the net present value assuming a rate of return : Calculate the net present value assuming a 17% rate of return (Ignore income taxes). Magna Inc. is considering modernizing production facility.

What will be your target industry : You have decided to start an OD consulting firm after you finish your MHR degree. What will be your target industry? What will you specialize in? How are you.

Write a plan for conversation you would have with employee : Write a plan for the conversation you would have with the employee, based on the concepts found in your textbook. What are the most important points you would.

Calculate revenues needed to obtain target operating income : How man haircuts have to be provided to earn an operating income of $80,000? To breakeven? Calculate the revenues needed to obtain the target operating income

User Account

All Pages