10
$\begingroup$

We were assigned to draw NFA for regular expression a|b|c, so like any one I draw this

wrong way?

But my professor told me it is wrong, the correct way is

correct way?

So, I checked it on online tools toolbox by cyberzhg, and regexper and according to both of them I am also correct.

Professor's argument was in maths for 4+5+1, we first add either 4+5 or 5+1 together then we add result of it with the remaining number. That is why for a|b|c, the correct solution is either (a|b)|c or a|(b|c).

Can you please tell are we both correct?

$\endgroup$
4
  • 7
    $\begingroup$ Your professor might have said that you should use Thompson's algorithm, which, in it's simplest implementation, gives their answer and not yours. (Or it might give a different answer if `|' is considered to be right associative.) But based on the professors explanation, it sounds like this is not the case. I would like to see how the professor adds 43242 + 33543 + 34325 by hand. $\endgroup$ Dec 4, 2021 at 22:58
  • 1
    $\begingroup$ Oh I just realised the professor did mention Thompson's notation $\endgroup$ Dec 6, 2021 at 3:56
  • $\begingroup$ Maybe "Thompson's Construction" is the right term rather than Thompson's notation or algorithm. Fun fact: this was invented by Ken Thompson while he was a master's student. Did you ever wonder why regular expressions are so prevalent in Unix? $\endgroup$ Dec 13, 2021 at 17:55
  • $\begingroup$ @TheodoreNorvell No sir, I don't know! You tell me. $\endgroup$ Dec 14, 2021 at 18:54

1 Answer 1

22
$\begingroup$

There is no unique way of converting a regex into NFA. That is, for any regular language $L$ there exist multiple (even, infinite) number of NFAs that accept the language $L$.

The solution of your professor restricts each state to have at most 2 outgoing states, while your solution does not. Unless this restriction was required by the professor somehow, both solutions are equivalent in the sense they both accept the language $L=\{a, b, c\}$ defined by the regexp a|b|c.

Note, that the professor might wanted you to work in methodological way, where there are fixed "gadgets", i.e., converting x|y to some certain states, and converting xy to other (fixed) states. Then, their comment makes sense - they wanted you to interpret a|b|c as (a|b)|c, first use the gadget on a|b to obtain the upper half of the machine, and then use the gadget again on x|c where $x$ is the already-constructed machine. If this (or any fixed other) methodology was required, then the outcome NFA would be unique.

$\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.