Write a regular expression equivalent to the following The s

Write a regular expression equivalent to the following: The set of all strings in which every pair of adjacent 0\'s appears before any pair of adjacent 1\'s. Also: The set of all strings with at most one pair of consecutive 0\'s and at most one pair of consecutive 1\'s.

Solution

regular expression for all the strings in which every pair of adjacent zeros appears before any pair of adjacent ones
A regexp that does match the required language is
0(100)(110)1.
It works as follows.

0(100) matches the empty string and any non-empty string that doesn\'t contain 11 and that ends with 0. The string can\'t contain 11 because there must be at least one 0 between every two 1s.

(110)1 matches every string that begins with 1 and does not contain 00, since there must be at least one 1 between any two 0s.

Now put the two halves together. If a string has the property that all occurrences of 00are before the first 11, then the section of the string before the first 11 must either be empty or end in 0, so it matches the first part of the regexp. The rest of the string contains no occurrences of 00 so it matches the second part of the regexp.

Note that there are shorter regexps that do the same thing: (0+10)(1+10) . That\'s a tidier version of the same idea.

Ther set of all strings with at most one pair of consecurtive 0\'s and at most one pair of consecutive 1\'s
(1+^)(10)*(0+^)+(0+^)(01)*(1+^)+11+00