Give a regular expression which denotes the language L over

Give a regular expression which denotes the language L over (0, 1) for each of the languages described below. All strings that begin or end with 00 or All strings that have exactly one occurrence of 00. All strings that do not have the substring 000.

Solution

(a) The regular expression can be categorized into two subparts.
R=L1+L2
L1 = The strings which begin with 00 or 11.
L2 = The strings which end with 00 or 11.
Let us find out L1 and L2.
L1 = (00+11). (any number of 0\'s and 1\'s )
L1 = (00+11).(0+1)*
Similarly L2 = (any number of 0\'s and 1\'s ) . (00+11)(00+11) = (0+1)*(00+11)
Hence R= [(00+11)(0+1)*]+[(0+1)*(00+11)]