What language is accepted by the Turing machine M = (q_0, q_1, q_2}, {q, b}, {a,

Question

What language is accepted by the Turing machine M = (q_0, q_1, q_2}, {q, b}, {a, b, }, delta, q_0, {q_3}) with delta(q_0, a) = (q_1, b, R), delta (q_1, a) = (q_1, b, R), delta (q_1, b) = (q_1, a, R), delta(q_1, ) = (q_2, , L), delta (q_2, a) = 9q_3, a, R) (ii) What language is accepted by the Turing machine M = ({q_0, q_1, q_2, q_3}, {a, b}, {a, b, }, delta, q_0, {q_2}) with delta(q_0, b) = (q_1, b, R), delta (q_1, a) = (q_1, a, R), delta (q_1, a, R), delta (q_1, ) = (q_2, , L), delta (q_0, a) = (q_3, a, R), delta (q_3, b) = (1_3, b, R), delta(q_3, a) = (q_3, a, R), delta (q_3, ) = (q_2, , L),

Explanation / Answer

Turing machine of your first question accepts a string over (a,b)* such that the string matches a regular expression a(a,b)*a

how it does so?

turing in state q0 only accepts a and goes to state q2 (so starting alphabet is a)

In state q1 it accept both alphabets and retains its state unless blank is encountered. Once blank is encountered its moves left and changes state to q2. (So this state accept (a|b)* )

When the Turing machine is in state q2, its head is on the last alphabet of the given string. In this state it accept only the alphabet a and goes to final state.

_---------_--------_--------_-------_--------_--------_--------_-------_--------_--------_--------

The second Turing machine accept a string ba* | a(a|b)*

how it does so?

Starting state accept both alphabets, branching out in two different branches. Let's first look into the branch when q0 accepts the alphabet a

q0 accepts b and goes to state q1 (so starting alphabet is b)

q1 accepts only a and retains its state, but once it encounter blank it goes to final state q2. (So q1 accepts a*)

So this branch accept ba*

When q0 accepts the alphabet a

q0 accepts a and goes to state Q3.(so the stating alphabet is a)

q3 state accept both alphabets and retain the same state, but once it encounter blank it goes to state q2.(so this state accept (a|b)*

So this branch accept a(a|b)*

I hope the way I explained helped you. Please let me know if you have any doubt. I shall be glad to help you with the same.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.