Search code examples
regexfinite-automata

Constructing finite state automata corresponding to regular expressions. Are my solutions correct?

I have drawn my answers in paint, are they correct?

(4c) For the alphabet {0, 1} construct finite state automata corresponding to each of the following regular expressions:

(i) 0

4ci

(ii) 1 | 0

4cii

(iii) 0 * (1 | 0)

4ciii

Solution

  • The first two are correct, although the first one might be able to be written as (depending on your convention)

    (0) -- 0 --> ((1))

    The last one is also correct, but can be simplified to (whenever you have ε appearing, there is likely to be a way to compress the edges and states together to remove it)

      +- 0 -+
  |     |
  v     |
 (0) ---+
 / \ 
1   0
 \ / 
  v
((1))

    (Excuse my ascii diagrams. I'm using (..) for each state, and ((..)) for final states.)

    Notice that the 0* is basically a loop from a state to itself, since after reading a 0 the remaining regex to match is the same (as long as we aren't at the end of a string).