The language accepted by this TM is all words with an odd number of letters that

Question

The language accepted by this TM is all words with an odd number of letters that have a as the middle letter. Show that this is true by explaining the algorithm the machine uses and the meaning of each state. Pay attention to the two necessary parts that must always be demonstrated.

a. Anything that has an a in the middle will get HALT.

b. Anything that gets to HALT has an a in the middle.

a,a (b,#,L) (a, H,L) a, a (b,b.L) (A,A,L) (#,#,L) (a,a,R) (b,b,R) (a,a.R) (b,b,R) (b,# R) START 4 (a, #, R) (b,b,R) (a,a, R) (#,#,R) A,A,R) HALT

Explanation / Answer

The algorithm used by the turing machine to accept the language is as follows:-

Step 1:

If we see a 'b' in the tape then we make it # and move right. This is where we start i.e the START 1 state and move to STATE 2. Now, if we get an 'a' as the first symbol ,then also we make it # and move right and goto STATE 3.

Step 2:

If the first symbol is 'a' then we have made it # and moved to STATE 3 in Step 1. Now in STATE 3 if we get a BLANK symbol (That means the language is just {a}) then we keep it BLANK symbol move right and we HALT.This is true as {a} is in our language.

Step 3:

If the first symbol is either 'a' or 'b' then have moved to STATE 2(if starting symbol was b) or STATE 3(if starting symbol was a).Now, if we have a next symbol following as 'a' or 'b' then we keep it as 'a' and move right and we keep it as 'b' and move right to STATE 4.In STATE 4 also we keep on moving right still we get a BLANK SYMBOL.

Step 4:

Once we get a BLANK SYMBOL IN STATE 4 we move left and goto STATE 5 OR if we get a # in STATE 4 we keep it # and move left and goto STATE 5.

Step 5:

In STATE 5 if either it is 'a' or 'b' we make it # and move left and goto STATE 6.In STATE 7 also we keep on moving left by keeping the symbols as it is.

Step 6:

In STATE 7 if we get a # then we keep it # and move right and continue from STATE 1.

Till here we are just matching the symbols to track that 'a' is in the middle.

Now in STATE 1 after matching if we get an 'a' and the next symbol of 'a' is # then, we are sure that 'a' is in the middle and we HALT.

If the next symbol of 'a' is not # then, we keep the next symbol as it is and move right to STATE 4 and contnue.

For example if the string is abbaaba

Then the tape will look as follows after each step:-

1.#bbaaba

2.#bbaab#

3.##baab#

4.##baa##

5.###aa##

6.###a###

7.HALT

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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