Log In
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
edited by

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)

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

1 vote
1 answer
Which of the following statements is/are TRUE? The grammar $S \rightarrow SS \mid a$ is ambiguous. (Where $S$ is the start symbol) The grammar $S \rightarrow 0S1 \mid 01S \mid \epsilon$ is ambiguous. (The special symbol $\epsilon$ represents the empty string) (Where $S$ is the start symbol) The ... are TRUE. Only (a) and (c) are TRUE. Only (b) and (c) are TRUE. All of (a), (b) and (c) are TRUE.
asked Nov 5, 2017 in Theory of Computation Arjun 2.2k views
1 vote
5 answers
What is the normal order of activities in which traditional software testing is organized? Integration Testing System Testing Unit Testing Validation Testing Code: c), a), b), d) c), a), d), b) d), c), b), a) b), d), a), c)
asked Nov 9, 2017 in IS&Software Engineering Devwritt 3.5k views
0 votes
2 answers
Which of the following is not a key issue stressed by an agile philosophy of software engineering? A. The importance of self-organizing teams as well as communication and collaboration between team members and customers. B. Recognition that change represents opportunity. C. Emphasis on rapid delivery of software that satisfies the customer. D. Having a separate testing phase after a build phase.
asked Nov 9, 2017 in IS&Software Engineering Devwritt 1.3k views
0 votes
3 answers
Software re-engineering is concerned with: A. Re-constructing the original source code from the existing machine (low-level) code program and modifying it to make it more user-friendly. B. Scrapping the source code of a software and re-writing it entirely from ... systems to make them more maintainable. D. Translating source code of an existing software to a new machine (low-level) language.
asked Nov 9, 2017 in IS&Software Engineering Devwritt 1.9k views