Assignment 2 (Due 8 March at End of Class)

General Rules:

a. Please hand in only your own work.
b. Grades discounted 10% per day late.

Tasks

1. Construct an FA which recognizes the r.e.:
a) 1*(001*)*
b) (((00)*(11))+01)*
2. Prove or disprove the following identities for regular expressions (where r, s & t are regular expressions):
a) rt + s = s + rt
b) (s + t)r = rs + rt
c) (r + s)* = r* + s*
3) Construct a Moore and Mealy machine that has the output of:
A -- when the input ends 011
B -- when the input ends 010
C -- otherwise
4) Write the r.e. for each of the following FAs ("e" means epsilon--empty string):
a) (q0,0) -> q0 (q0,1) -> q1 (q0,e) -> q2 (q1,1) -> q0 (q2,0) -> q3 (q2,1) -> q2 (q3,0) -> q2
n.b. (q1,0), (q3,1) are invalid moves. q2 is the final state.
b) (q0,0) -> q0 (q0,1) -> q1 (q1,0) -> q2 (q1,1) -> q1 (q2,0) -> q0 (q2,1) -> q1
q0 is the final state.