The length of the shortest string not in the language generated by the regular expression r =
(1 +01)00(1 +10)+(1+01)* $(0 + \in)$ over {0, 1} is equal to ________

Open in App

Solution

We have two ways to solve this, the first way being, check every string starting from 0 length it
it is generaged by the regular expression or not.
But if we observe the regular expression carefully, r is actually broken into two parts.
= (Exactly 1 pair of consecutive zeroes)+(No pair of consecutive zeroes)
= (At most 1 pair of consecutive zeroes)
So if we can recognize the language, we already know that the shortest string not generated will be the shortest string having more than one pair of consecutive 0's and it is none other than 000. So the length will be equal to 3.

Suggest Corrections

Similar questions

1^{*} 0 (0 + 1)^{*}

(0 + 1)^{*} 01^{*}

1^{*} 0 (1 + 0)^{*} + (0 + 1)^{*} 01^{*}

L_{1}

(0 + 1)^{*} 001^{*} a n d L_{2}

L_{1} \cap L_{2}

(o v e r \sum = {a, b})

a^{*} b^{*} (b a)^{*} a^{*}

{0, 1}

(0 + 1)^{*} 0 (0 + 1)^{*} 0 (0 + 1)^{*} ?

(10)^{2}

Join BYJU'S Learning Program