3. Find a regular expression for the set of all strings that don not end with 01, over (0, 1)*.
Solution:
We have the input alphabets ∑* = {0, 1}*
∴∑ = {0, 1}
Here, the resultant regular expression will denotes the set of all strings over the ∑ that do not ends with 01.
To fix this problem, first find out the different strings of length two from the symbols 0 and 1. It is –
00, 01, 10 and 11
According to the question, the resultant regular expression will denotes the set of all strings over the input alphabets ∑ that never ends with 01.
Thus, the strings can be ends with-
00, 10, and 11
Also, the regular expression which denotes the set of all strings over the input alphabets ∑, can be written as-
(0 + 1)*
Thus, the resultant regular expression can be written as-
(0 + 1)* (00 + 10 + 11)
