The language accepted by this Turing marching is all words with an odd number of

Question

The language accepted by this Turing marching is all words with an odd number of letter that have 'a' as the middle letter. Show that this is true by explaining the algorithm the machine used and meaning of each state. Pay attention to the two necessary parts that must always be demonstrated: (i) Anything that has an 'a' in he middle will get to HALT. (ii) Anythig that gets to HALT has an 'a' in the middle.
R 19 Turing Machines ems 1 and 2, consider the following TM: (b,b,L) (b,a,L) (b,b,L) (a,A,L) (a,a,L) (a,a,R) (b,b,R) 4 1 START (b,b,R) (a,#,R) a,a. R) HALT (a,a,R) (b,b,R)

Explanation / Answer

1. Start state
   if a comes, we put # and move towards right
   if b comes, we put # and move towards right
2. If either a or b comes, we don't modify anything and move towards right
3. If either a or b comes, we don't modify anything and move towards right
   if # or comes it halts
4. We ignore any number of 'a's and 'b's and move towards Right
   if or # comes, we move towards left
5. If a or b comes, we replace it by # and move towards L
6. If either a or b comes, we don't modify anything and move towards left
7. We ignore any number of 'a's and 'b's and move towards Left
   if # comes, we move towards right
  
Turing machine is strikes out first letter and last letter and does it again and again till we reach middle. Doing it so makes sure that we have even number of letters covered. If a is there at center, it Halts. Even letters + one 'a' gives odd letters.
  
Let's see the sequence now. We have 2 ways and 1 way to Halt
1 > 2 > 4 > 5 > 6 > 7 > 1
It is a sequence for striking first and last letters if the letter is b

1 > 3 > 4 > 5 > 6 > 7 > 1
If letter is a and there are some more letters which are not considered yet, then we will have to strike out one more letter

1 > 3 > Halt
A comes and there are no more letters.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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