How do I simplify this regex?

629 Views Asked by At

The regex is:

$$R=0^*10+0^*101+0^*10110^*$$

$$R=0^*10(\epsilon+1+110^*)$$

$$R=0^*10(\epsilon+1(\epsilon+10^*))$$

This is as far as I got and don't know how to simplify further.

If anyone was wondering, this is for finding the DFA which accepts strings that do not contain 110. I constructed a DFA that did accept 110, found its complement, and developed an expression which I am trying to simplyify

1

There are 1 best solutions below

1
On BEST ANSWER

To construct a DFA which accepts all strings not containing 110, you can't just use the negation of a DFA which does accept 110. You must use the negation of the DFA which accepts exactly those strings containing 110. The regular expression corresponding to the DFA accepting only strings containing 110 is $(0\cup1)^*110(0\cup1)^*$.

To negate this, simply switch the accepting and non-accepting states of the DFA (draw them!), and figure out the resulting regular expression, which is $0^*(100^*)^*1^*$. Note that this regex expresses strings where there are any number of single ones surrounded by zeros, and then any number of ones.