CameraIcon

SearchIcon

MyQuestionIcon

1

You visited us 1 times! Enjoying our articles? Unlock Full Access!

The length of...

Question

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

thumbs-up

0

Similar questions

Q. Consider the following regular expressions over the alphabet {0, 1}

I.

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

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

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

Which of the above regular expressions are equivalent?

L_{1}

be the language corresponding to the regular expression

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

be the language correponding to the regular expression 110(1+0)*. Which of the following is the regular expression corresponding to the language

L_{1} \cap L_{2}

?

Q. The length of the shortest string NOT in the language

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

of the following regular expression is

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

Q. Which one of the following languages over the alphabet

{0, 1}

is described by the regular expression:

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

Q. Consider the following regular expressions over {0, 1} respectively.
I. 101 (0 + 1)* 101
II. 101 (0 +1) * 101 +

(10)^{2}

1
III. 101 (0 + 1)*

Which of the above regular expression(s) correctly generate the set of all binary strings starting and ending with 101?

View More

Join BYJU'S Learning Program

Join BYJU'S Learning Program

CrossIcon