1
$\begingroup$

enter image description hereWe were given a question in class with this FSM and had a debate over what the regex would be and the corresponding accepted strings. Does this FSM make sense as on state 1 there seems to be a choice between going to state 3 or looping on state 1 with the input of b.

![enter image description here][2]

Please forgive the bad drawing as we were given the question on paper.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Which state is initial, and which are final? $\endgroup$ – nekketsuuu Mar 7 '17 at 10:22
  • $\begingroup$ @nekketsuuu sorry, was trying to draw it quick. S0 is start, S3 is accepted $\endgroup$ – Samiko Mar 7 '17 at 10:23
  • $\begingroup$ Hint: What is the corresponding FSM of a regex $a^{*}b$? $\endgroup$ – nekketsuuu Mar 7 '17 at 10:25
  • $\begingroup$ @nekketsuuu that wasn't the question, I was asking whether you can have one input with a choice to stay in S1 or go to S3 whilst at S1. In this case, for the input b $\endgroup$ – Samiko Mar 7 '17 at 10:29
  • 1
    $\begingroup$ Do you learn NFA? $\endgroup$ – nekketsuuu Mar 7 '17 at 10:33
2
$\begingroup$

The diagram appears to be of a Nondeterministic finite automaton, or NFA. A NFA is a model of a theoretical machine that accepts a given string if any path through the NFA for that string can end up at an accepting node.

So the simple answer to the question in the title is "yes, if you're talking about NFAs". (As opposed to Deterministic finite automata, or DFAs, which must have a unique outgoing edge for each character at a given node)

One traditional way to write a program to check if a string is accepted by an NFA is to keep track of all the states that the machine could be in after seeing a particular character, and then at the end declare that the string is accepted if one of the states we could be in now is an accepting state.

For example, consider the input string abbbbb.

At the start, the machine can only be in state $S_0$, so the set of states it can be in is $\{S_0\}$.

After a, the machine can now only be in $S_1$, so $\{S_1\}$.

After ab, the machine could be in $S_1$ or it could be in $S_3$, so $\{S_1, S_3\}$.

After abb, the machine's set of possible states is $\{S_1, S_2, S_3\}$.

After abbb, the machine's set of possible states is $\{S_1, S_2, S_3\}$.

After abbbb, the machine's set of possible states is $\{S_1, S_2, S_3\}$. You should see a pattern by now.

And in fact, at the end of the whole input string abbbbb, the machine's set of possible states is $\{S_1, S_2, S_3\}$, and that contains an accepting state ($S_3$), so the string is accepted.

The regular expression should now be easily readable from the machine: ab*(a|b)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Perfect, thank you! My tutor had not mentioned anything to do with NFAs or DFAs so I must assume we only learn about the former. This makes sense and explains it better than he could've. I will ask directly next class for more details. Sorry if it seemed like an obvious question $\endgroup$ – Samiko Mar 7 '17 at 16:07

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.