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.

Sebastian Danicic BSc MSc PhD (Reader in Computer Science)
Dept of Computing, Goldsmiths, University of London, London SE14 6NW
Last updated 2011-03-15