4. Find a regular expression for the set of all strings that begin or end with 00 or 11 over {0, 1}.
Solution:
We have the input alphabets ∑ = {0, 1}
Here, the resultant regular expression will represent the set of all strings over the given ∑ that being or ends with 00 and 11.
The regular expression for the set of strings over the given ∑ can be written as-
(0 + 1)*
Thus the resultant regular expression can be written as-
(00 + 11)(0 + 1)*(00 + 11)
