The Gateway to Computer Science Excellence
+2 votes

Which of the following regular expressions, each describing a language of binary numbers (MSB to LSB) that represents non-negative decimal values, does not include even values?

$(1)\ 0^*1^+0^*1^*$        $(2)\ 0^*1^*0^+1^*$        $(3)\ 0^*1^*0^*1^+$        $(4)\ 0^+1^*0^*1^*$

Where $\{+,\ * \}$ are quantification characters.

in Theory of Computation by Veteran (431k points)
recategorized by | 1.5k views

1 Answer

+3 votes
Best answer

When a number is represented in binary form, for odd numbers, we have a 1 in the LSB while a 0 in LSB for even numbers.

So, only the language generated by option (3) $0^*1^*0^*1^+$ will, for sure, have a 1 in the LSB. So, this language won't contain any even numbers.

Answer: option (3)

by Boss (17.8k points)
selected by

but it is not correct RE for odd numbers..

it will not accept 11110001110001,

the correct RE should be (0+1)*1

but among given RE's which does not accept even decimal eqvlnt, option 3 is correct..


Read the question again carefully. The question is asking that which of the given options will not contain even numbers. It is not asking for the regular expression for odd numbers. :)

i have already mentioned in my comment what you are saying..
Sorry, I said that before u edited
no problem :)

Rishabh Gupta 2

in question , it is also mentioned like non-negative ryt then, first digit should be 0 always then MSB should be like 0

can you pls clarify my doubt ?

thanks in advance

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,312 answers
105,038 users