enter image description here

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.


This might work:

enter image description here

  • $\begingroup$ 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)$. $\endgroup$ Nov 29 '13 at 1:06

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_7:X,X,R$ for X=a,c

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

  • $\begingroup$ 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? $\endgroup$
    – stackuser
    Nov 29 '13 at 2:18
  • $\begingroup$ 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$. $\endgroup$
    – abc
    Nov 29 '13 at 7:32
  • $\begingroup$ Good explanation, accepted answer. Yes, it seems like $w \notin L$ since $L$ does not allow a string to end in $a$ $\endgroup$
    – stackuser
    Nov 29 '13 at 16:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.