Search code examples
regexautomatadfa

Regular expression 0*1*1+11*0*1 DFA

Will the expression "0*1*1+11*0*1" be accepted by the following automaton?

enter image description here

As the expression generates strings ending with '1', I believe the automaton will accept it.

However, I found the answer to be otherwise in one of the references. Can someone please clarify it with explanation?

NOTE: + means OR operation.

Solution

  • No. Your DFA is equivalent to the expression (0*1+)+

    The expression that you've specified requires at least three 1 to be accepted. Breaking it down into parts

    0*
1*
1+ <-- Required at least once
1  <-- Required
1*
0*
1 <-- Required

    A DFA that is equivalent to your expression needs to represent this looks like this:

    enter image description here

    Image created with the Regex visualizer, which allows you to generate these graphs from regular expressions.

    Update: If + means or, this changes things. Your original DFA is still not equivalent. You're missing that if the accepted string starts with a 1 it will need to be followed by at least one more 1 to be accepted. The DFA for the expression looks like this:

    enter image description here

    As generated by inputting 0*1*1|11*0*1 into the visualizer.