Assignment I

Due date Feb. 6 for question 1, Feb. 13 for question 2.


1. The following grammar generates binary numbers with an interesting property. Non-terminals are A, B, S, terminals are 1 and 0. The root symbol is S. Productions are:
    S ::= S 0 | A 1 | 0
    A ::= B 0 | S 1 | 1
    B ::= A 0 | B 1
a) Show that the generated binary numbers are all multiples of 3.

b) Show that all multiples of 3 are generated by the grammar.
2. First programming assignment (in Ada).

In Ada, integer literals can be given in any base between 2 and 16. The base to be used appears as a prefix of the number, and the digits appear bracketed by sharp signs. For example, the following are valid representations of the number 7:

2#111# , 3#21#, 4#13#, 9#7#, etc.

For bases greater than 9, the valid digits are taken from the usual sequence A, B, C, D, E, F. The base itself is always given in base 10. For example, the number 2560 can be written: 16#A00#

The assignment is to write a program that reads a string representing a based number, and prints the corresponding decimal value of the number. You can use your favorite programming language, to get the algorithm right, but you have to submit a version in Ada as well. If you are new to the language, The Input/output primitives that you need are the following:

a) Get_Line (Line, last) reads one line from the input file, and sets Last to the number of characters read. You should declare Line to be a string of 100 characters, long enough for our purposes.

b) Put_Line (Str) prints a line on the output file. To print integers, use the image attribute, as follows: Put_Line (Integer'Image (X));
The outline of the program should be:
with ada.text_io; use ada.text_io;
procedure Based_Numbers is
   Line : String (1..100);
   Last : Integer;
   Val  : Integer;
begin
   loop
      Get_Line (Line, Last);
      exit when ..     -- choose some termination condition
      .... scan the number, do the conversion, report illegal input, etc.
      Put_Line (Integer'image (Val));
   end loop;
end Based_Numbers;