# Turing machine with possible transitions to the final state [closed]

Let's say we want to draw the transition graph of a Turing Machine that accepts that language L and then write the sequence of moves done by the TM when the input sequence is $w = abbcbba$ so I had some thoughts on how this could be built.

$q0 - q1: a,a,R$

$q1-q2: b,b,R$

$q2 (loop): b,b,R$

$q2-q3: c,c,R$

$q3-q4: b,b,R$

But then I'm getting stuck here, I could see $b,b,R$ to the final state and then add a separate node to account for the case $m=3$, but I'm teaching this to myself so maybe someone can step in here and get me back on track.

EDIT:

This might work:

• As a note: this machine makes one pass from left to right over the input (without rewriting it) so you could classify it more or less as a finite state automaton. It is easily seen the defined language is regular: $ab^*c(b+bb+bbb)$. Nov 29 '13 at 1:06

## 1 Answer

I would define F(set of final states)={$$q_4,q_5,q_6$$} then:

$$q_4-q_5:b,b,R$$

$$q_4-q_7:X,X,R$$ for X=a,c

$$q_5-q_6:b,b,R$$

$$q_5-q_7:X,X,R$$ for X=a,c

$$q_6-q_7:X,X,R$$ for X=a,b,c

• That gets me going +1, great. But I want to make sure that I understand what you're saying. And also, which was part of my post, to check that test string $w$. How would you correct what I've added? Nov 29 '13 at 2:18
• The exercise seems to be correct, $w \notin L$ and the TM stops itself in $q_7$ but $q_7 \notin F$ so M correctly doesn't accept the string $w$.
– abc
Nov 29 '13 at 7:32
• Good explanation, accepted answer. Yes, it seems like $w \notin L$ since $L$ does not allow a string to end in $a$ Nov 29 '13 at 16:21