Question

Write regular expressions that describes the following language:

The language over {0,1} that contains all and only the strings that are base-2 representations of odd positive integers. Do not allow leading 0s. (If you are more comfortable writing bulky regular expressions than you are working in base-2, you may write a regular expression for strings that are base-10 representations of odd integers without leading 0s, using alphabet {0,1,2,3,4,5,6,7,8,9}.)

Answer 1

The idea for the regular expression is as follows: As there are no leading , the integer must start with . As it is supposed to be odd, it means that there is a at the end of the base-2 representation of the integer. There can be anything in the middle.

Therefore the expression is:

To understand this expression, there are two cases:
There is only one digit in the integer. In this case, that digit must be .
There is more than one digit. In this case, the leading digit must be , the ending digit must be , and anything can appear in the middle.

Therefore the given regex corresponds to what is needed. Comment in case of any doubts.