EXERCISE # 1
------------

Construct transition diagrams corresponding to the following
regular grammars.

a) G1 = ( {S,A,B,C,D}, {a,b,c,d}, P, S ), where P consists of

		S -> aA			S -> B
		A -> abS		A -> bB
		B -> b			B -> cC
		C -> D
		D -> bB			D -> d

a) G2 = ( {S,A,B,C,D}, {a,b,c,d}, P, S ), where P consists of

		S -> Aa			S -> B
		A -> Cc			A -> Bb
		B -> Bb			B -> a
		C -> D			C -> Bab
		D -> d

Formally specify each corresponding FSA.
Use your transition diagrams to construct a left-linear grammar
for L(G1), and a right-linear grammar for L(G2).  
Check your answers by constructing derivation sequences for the
following strings:

a) for G1: abb aababb b cd cbb
b) for G2: a aba aabca dca


EXERCISE # 2
------------
Construct a regular expression denoting the language of statement
lists.  A statement list is a list of basic or dummy statements.
Each statement in the list is separated from the next by one or
more semi-colons.  In addition each statement may be labeled an
arbitrary number of times.  For example,

				   b;l:b;l:l:;;b;;

is a statement list, where 'l' denotes a label and 'b' denotes a
basic statement.  Assume 'l' and 'b' are terminal symbols.


EXERCISE # 3
------------
In class we built the following regular expression for Floating Point
Constants: 

F =  S (D* '.'? D+ | D+ '.'? D*) (S ('e' | 'E') D+)?

where S = '+' | '-' | empty
and
      D = '0' | '1' ... '9'

Investigate the rules for Floating Point Constants in two
different programming languages (C, Java etc.)
and refine the regular expression if necessary.


EXERCISE # 4
------------
Convert the following regular expression to a NFA, then
transform  the  NFA  to  a right-linear regular grammar, and
finally  transform  the  grammar  to  the  original  regular
expression.  Show your work.
		
      (a|b)* f* (b* (c*d)* | e)* (g | h)*