CODEWITHSUNDEEP
regexfinite-automata
Danny Rancher
Danny Rancher

Reputation: 2005

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

Upvotes: 0

Views: 271

Answers (1)

huon
huon

Reputation: 102066

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).

Upvotes: 2

Related Questions