Regular expression in theory of computation solved examples Part 4

Solution:

We have the input alphabets ∑ = {0, 1}

Here, the resultant regular expression denotes the set of all strings over the given ∑ which does not contain a substring 000.

Here, we can describe the given statement i.e., “The resultant regular expression does not contain any string which has a substring 000”, in the following other ways-

1. a) No any zero is immediately followed by the substring 00.

Here, following are the substrings of length 2 which can be immediately followed by a single zero over the given input alphabets ∑ = {0, 1}-

                        00, 01, 10 and 11

But from statement (a) no any zero can be immediately followed by the substring 00.

Thus a single zero can be followed by the substring 01, 10 and 11.

Thus the string under the resultant regular expression can contain the substrings-

                        001, 010 and 011                    (1)

1. b) Substring 00 can’t be immediately followed by a single zero.

Here, the substring 00 can be followed either by 0 or 1 (since length of the given substring, i.e., 000 is 3).

But from statement (b) substring 00 can’t be immediately followed by 0.

Thus, substring 00 can be followed by 1 only.

Thus the strings under the resultant regular expression can contain a substring-

                        001                  (2)

1. c) Any substring of length 3 whose both first and last symbol is ‘0’ does not contain ‘0’ as its middle symbol.

Thus, this substring can contain only ‘1’ as its middle symbol.

Thus, strings under the resultant regular expression can contain the substring-

                        010                  (3)

From equation (1), (2) and (3), we can get the form of resultant regular expression-

                        (001 + 010 + 011 + 001 + 010)*

Removing the duplicates, we get-

                        (001 + 010 + 011)*

But, this regular expression contains λ, the empty string, which is not required. Thus the resultant non-empty regular expression is-

                        (001 + 010 + 011) (001 + 010 + 011)*

or, we can also write it as-

                        (001 + 010 + 011)+

This is the resultant regular expression.