1
$\begingroup$

I am trying to generate a transition graph for a turing machine that accepts the languages of all strings that do not contain the substring $bbb$ with the input alphabet $\Sigma = \{a, b\}$.

When I implement this graph in JFLAP, I'm receiving an error that there are transitions out of final states. Is it OK to construct a transition graph like this, or is it considered bad practice? If so, can you help me understand the correct way to construct the transition graph?

enter image description here

$\endgroup$
4
  • $\begingroup$ What exactly means the label over edges? What is JFLAP? the question is about how to typing correctly input graph to JFALP? $\endgroup$ – Jonathan Prieto-Cubides Dec 9 '14 at 0:45
  • $\begingroup$ It signifies the operation of a Turing Machine. For example, the link that goes from 'q0' to 'q0' is a; a; R (read a, write a, move right). $\endgroup$ – Rusty Dec 9 '14 at 1:55
  • $\begingroup$ I think it's better or more common just labeled with the symbol. But, That's 0k. Non problem. $\endgroup$ – Jonathan Prieto-Cubides Dec 9 '14 at 2:01
  • $\begingroup$ Actually, I get the same automaton. For me, It seems to be good just for q3 state. The state q3 it's not an final state, because your language doesn't accept .*bbb.* pattern in strings. So You shouldn't be. $\endgroup$ – Jonathan Prieto-Cubides Dec 9 '14 at 2:08
1
$\begingroup$

The state $q_3$ is not necessary, because you couldn't have string with the pattern $bbb$ inside of them. So, just delete it. The next automaton accepts your language requirement.

enter image description here

Hope it helps

$\endgroup$
1
$\begingroup$

what you can do with that Jflap issue is that just remove the q3 from your turing machine and add new state and make an empty transition from all the final state to the new state added, make the new state as final state and change all previous final state i.e. q0, q1 and q2 to non final state your issue with jflap will be resolved here's your required turing machine enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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