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$
  • $\begingroup$ What exactly means the label over edges? What is JFLAP? the question is about how to typing correctly input graph to JFALP? $\endgroup$ – jonaprieto 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$ – jonaprieto 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$ – jonaprieto 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$

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.