Formally expressing regular expression

628 Views Asked by At

Supposed there is a set of all strings in 0, 1 which is a set of all strings obtained by concatenating a sequence of zeros or more strings.

With this definition, I'd express all strings containing the substring $000$ as $(0 + 1)^*000(0 + 1)^*$ where $+$ represents union.

With this formal expression of regular expression, how can I express a set of strings that contain exactly one occurrence of substring 010 ?

1

There are 1 best solutions below

2
On BEST ANSWER

I like to solve these fiddly problems by working out the right DFA (state machine) and then converting to a regular expression. So first what does a string that doesn’t contain $010$ look like?

Well if you see a 0 then you’re allowed another 0 or 11. If you see a 1 (and aren’t followed by a zero then you’re allowed anything you like. So the regular expression for something not containing $010$ (and not ending in 0) is $\left(1^*(0^*11)^*\right)^*$. Thus an expression for something containing 010 exactly once is: $$\left(1^*(0^*11)^*\right)^*0^*010\left(\epsilon + 0^*1 + 0^*11\left(1^*(0^*11)^*\right)^*0^*1^*\right)$$ There’s probably a simpler way to express it.