Regular expression in theory of computation solved examples Part 4

Solution:

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

Here, the resultant regular expression will denotes the set of all strings having atmost one pair of 0’s or atmost one pair of 1’s.

Here, atmost one pair of 0’s means, there is either one pair of 0’s, i.e., 00 or no one pair of 0’s.

Similarly, atmost one pair of 1’s means, in the string which will be represented by the resultant regular expression, there is either one pair of 1’s, i.e., 11 or no one pair of 1’s.

For getting such regular expression, first we have to find the language denoted by this problem-

                        0*        = {λ, 0, 00, 000, 0000, 00000, .. .. .. ..}                      (1)
01*      = {0, 01, 011, 0111, 01111, 011111, .. .. .. .. ..}        (2)
1*        = {λ, 1, 11, 111, 1111, 11111, .. .. .. ..}                      (3)
10*      = {1, 10, 100, 1000, 10000, 100000, .. .. .. .. ..}         (4)

Now , from the equation (1), (2), (3) and (4), we can easily find out that which regular expression does not contain a pair of 0’s i.e. 00.

Thus, here the regular expressions-

                        1* and 01*

does not contain a pair of 0’s.

We can write these two of 0’s as-

                        (1* + 01*)                                           (5)
Now, to find the regular expression that contains exactly one pair of 0’s, we simply write the regular expression which does not contains a pair of 0’s on the both side of the pair of 0’s, i.e. 00. Thus, the regular expression which contains exactly one pair of 0’s can be written as-

                        (1* + 01*) 00 (1* + 01*)                     (6)

Now, similarly we can easily find out that which regular expression does not contain a pair of 1’s, i.e., 11.

Thus, here the regular expressions-

                        0* and 10*

does not contain a pair of 1’s.

We can write these two of 1’s as-

                        (0* + 10*)                                           (7)

Thus, (0* + 10*) is a regular expression that contains no pair of 1’s.
Now, similarly to find the regular expression that contains exactly one pair of 1’s, we simply write the regular expression which does not contains a pair of 1’s on the both side of the pair of 1’s, i.e. 11. Thus, the regular expression which contains exactly one pair of 1’s can be written as-

                        (0* + 10*) 11 (0* + 10*)                     (8)

Thus, from equation (5), (6), (7) and (8) we can find the regular expression over input alphabet {0, 1} having atmost one pair of 0’s or atmost one pair of 1’s. Thus, the resultant regular expression is-

                        (1* + 01*) + (1* + 01*) 00 (1* + 01*) + (0* + 10*) + (0* + 10*) 11 (0* + 10*)