2 Regular Expressions, Finite State Machines and Recognisers

1. Draw Finite State Machines for the following Regular Expressions
   1. $a^*b$

   2. $((a \vert b)cd)^*$

   3. $((a \vert b)cd)^*)\vert(a^*b)$

   4. $(a\vert b^*)(c \vert d)$

   5. $((a\vert b^*)(c \vert d))^*a$

2. Here is a recogniser for $a^*b$.

   rec1: list(char) -> bool;
   rec1(nil) <= false;
   rec1(x::nil) <= x='b';
   rec1(x::y::m)<= x='a' and rec1(y::m);
   

   Write recognisers list(char) -> bool; for each of the other languages above.

3. Make up five more regular expressions, draw FSMs for them and write the recognisers.