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 (as above, you can use base-10 if you prefer) representations of rational numbers. Define a representation of a rational number to be either a representation of an integer, or two representations of integers separated by “/”. Leading 0s are allowed this time.

Answer 1

The idea for this is as follows:

There are two cases to consider:
First case is that "/" appears in the number. In this case, there must be an integer that precedes the "/" and then one that follows. Note that the one that follows after "/" is the denominator, hence it must not equal , otherwise it is not a rational number. This means that there must be a appearing somewhere in the expression.
Second case is that "/" doesn't appear in the number. In this case, it simply has to be an integer, therefore it's base-2 representation can be any finite string.

Hence the regex is the following:
.

The first part of the regex is for expressions with "/". The second part is for expressions with "/", in which the denominator must contain a , as noted above.

Comment in case of any doubts.