1. Write a lex description for the language of all strings of digits 0...9
that have nodigit repeated. (example: 02529 is not allowed since the digit 2 is
repeated). HINT: Remember the operations under which regular sets are
closed. 
Your lexical analyzer should print "ACCEPT" or "REJECT",
as apprporiate. To reduce complexity, use the following LEX definitions
whenever appropriate:

D  [0-9]
S {D}*

2. a. Construct a Finite State machine M, that will accept the following 
regular expression: (a|b)*a(a|b)
b. Construct the minimal deterministic state machine for M

3. Construct a non-deterministic finite state machine for the regular 
expression ((epsilon | a)b*)*

4. Show that the following grammar is ambigous:

S --> ABS|0
A --> BA|epsilon
B --> SA|2

More useful exercises from the Dragon book, Chapter 3:
Problems: 

3.3.2 a,b,c,d 
3.3.5 a,f,h,i

3.7.3 a,b 
Also: 
construct minimum state DFA's for the DFA's in 3.7.3 a) and b) 
(obtained using subset algorithm) and prove that the regular 
expressions in 3.7.3 a) and b) are equivalent by showing that 
there minimum state DFA's are the same (except for state names)