Clever Geek Handbook

Simplifying Regular Expression

I have a really simple question (edit on the right).

What is the simplest form of this regex?

(((0|1)*(00)(0|1)*)((0|1)*(11)(0|1)*))|(((0|1)*(11)(0|1)*)((0|1)*(00)(0|1)*))

I am creating a regex that accepts the language for all binary strings containing substrings 00 and 11 (in any order).

Now I have an expression, but I'm sure it can be simplified.

+3


source to share


1 answer


They are almost the same regular expression. I just converted (0|1)

to [01]

, added [01]*

left and right, common to both cases (first or first first), and removed some parentheses that were not needed:

[01]*(00[01]*11|11[01]*00)[01]*


Steps to reproduce

  • Indication with

    (((0|1)*(00)(0|1)*)((0|1)*(11)(0|1)*))|(((0|1)*(11)(0|1)*)((0|1)*(00)(0|1)*))


    __^^^^^_____^^^^^___^^^^^_____^^^^^______^^^^^_____^^^^^___^^^^^_____^^^^^___

  • Replace everything (0|1)

    with[01]

    (([01]*(00)[01]*)([01]*(11)[01]*))|(([01]*(11)[01]*)([01]*(00)[01]*))

    _______^^^^____________^^^^_______________^^^^____________^^^^_______

  • Remove the parentheses around (00)

    and (11)

    since you do not want to grab this group and you do not *

    , +

    , ?

    behind the bracket. Therefore this is not required due to the ambiguity.

    (([01]*00[01]*)([01]*11[01]*))|(([01]*11[01]*)([01]*00[01]*))


    _^____________^^____________^___^____________^^____________^_

  • Remove another parenthesis that doesn't resolve any ambivalence:

    ([01]*00[01]*[01]*11[01]*)|([01]*11[01]*[01]*00[01]*)


    ________^^^^^^^^^^_________________^^^^^^^^^^________

  • Collapse [01]*[01]*

    in [01]*

    , which means exactly the same thing.

    ([01]*00[01]*11[01]*)|([01]*11[01]*00[01]*)


    _^^^^^_________^^^^^___^^^^^_________^^^^^_

  • Extract common prefix and suffix [01]*

    [01]*(00[01]*11|11[01]*00)[01]*

+5


source






More articles:


All Articles