Assignment I

Due date Feb. 12, 2004.


1. From text, page 726, section 2.2, problem 1.

2. Page 727, Section 2.3, problem 1 (c).

3. Write a regular expression over the alphabet {0,1} that generates the binary numbers that are multiples of four.

4. Draw the DFA that recognizes floating-point numbers with and without an explicit exponent. Both the integer and the decimal part must have at least one digit, and be separated by a period. The exponent can include a sign.

5. Numeric literals in Ada can be given in a base different from 10. The following are the relevant productions:
based_literal  ::=   base # based_numeral #
base           ::=   numeral
numeral        ::=   digit | digit numeral
based_numeral  ::=   extended_digit | extended_digit based_numeral
extended_digit ::=   digit | A | B | C | D | E | F

This allows us to write octal numbers   8#7717#, hexadecimal numbers like
16#DEADBEEF#, and numbers in less common bases like 5#123123# or 12#AAB9#.
The base itself is always interpreted as a number in base 10.

The rules above do not forbid strings that are meaningless because they include digits that are larger than the base, for example 8#88#, or 3#ABC#. How many rules would we need if we wanted a regular grammar that only specified legal numerals? Do not list them all, a rough estimate is sufficient.