# Find regular expression that defines a given language

I want to find a regular expression that defines a language L over the alphabet {0,1} with a following condition: every word contains exactly two 000 substrings. For example, a valid word would be 1010001010001111, but not 101000011 (even though there are two 000 substrings - 0000 and 0000).

Now, a language that has exactly one 000 substring over the {0,1} alphabet is, if I'm not mistaken: (1 + 01 + 001)* 000 (1 + 10 + 100)* (which equals some X, for example).

Would the solution to the first problem be X 1 X? Or am I missing something? Any constructive input would be greatly appreciated.

• As far as I understand, XX would mean that one of the possible words could be 000000, thus there would be more than two 000 substrings (the solution requires exactly two). – emppu May 28 '15 at 15:54
• X doesn't need to recognize 0^4. – emppu May 28 '15 at 16:17
• Might be that we understand the problem differently... From the first paragraph in my question: "For example, a valid word would be 1010001010001111, but not 101000011 (even though there are two 000 substrings - 0000 and 0000)." Although, it does not say that I can't have 0^4. Not a very clear question in my textbook, I guess. P.S. Sorry for my slow responses, still trying to work it out on paper. – emppu May 28 '15 at 16:27
• Sould $\mathtt 0^6$ be in the language? – Henning Makholm May 28 '15 at 16:54
• No, as it would contain more than two 0^3 substrings. – emppu May 28 '15 at 16:59

First I try a definition of what it means for a word to have $k$ substrings $s$:

A word $w$ contains a substring $s$ if $w=usv$ for some words $u$ and $v$ otherwise it contains no ($0$) substrings $s$.

If $uv$ does not contain a substring $s$ then $usv$ contains $1$ substring $s$.

If $uv$ contains $k$ substrings $s$ then $usv$ contains $k+1$ substrings $s$.

Then I try to specify the language with no substring $s=0^3$: $$L_0 = (1|01|001)^*(\epsilon|0|00)(1|10|100)^*$$

Now I try to add the substring at all places of $L_0$ and come up with a combined expression:

$$L_1 = (1|01|001)^*(0^3|0^4|0^5)(1|10|100)^*$$ contains all words which contain $1$ substring $0^3$.

Finally I try to add another $s$ at every place: \begin{align} L_2 = & ((1|01|001)^*(0^6|0^7|0^8)(1|10|100)^*)|\\ & ((1|01|001)^*(0^3|0^4|0^5)(1|10|100)^*1(0^3|0^4|0^5)(1|10|100)^*) \end{align} contains all words which contain $2$ substrings $0^3$.

Testing:

I wrote some Ruby code (link) to test the above regular expressions.

It generates random strings and checks if the above regular expressions give the same results as some alternative test methods.

\$ ruby 2sub.rb
test (l0, m0) with 100000 samples up to length 50 ..
done.
test (l1, m1) with 100000 samples up to length 50 ..
done.
test (l2, m2) with 100000 samples up to length 50 ..
done.


This is not a proof, but gives some confidence that the results hold.

Try it. If you change tiny bits of the regexps you will notice the differences:

(..)
test (l2, m2) with 100000 samples up to length 50 ..
(..)
99944 [000001100001] [false true]!
99946 [011111011001100111110001000001] [false true]!
99947 [00010010010000010010100101] [false true]!
99950 [00101100011010100110101001101100010] [false true]!
99952 [0101100010100101101110001001011100] [false true]!
(..)