Skip to main content
1 of 2
Raphael
  • 73.4k
  • 31
  • 184
  • 406

In general, you can decide equivalence of regular expression and finite automaton using standard algorithms:

  • Construct an NFA from the regular expression,
  • Determinise and minimise both automata,
  • Check for equality (up to isomorphism).

These algorithms and proof that the minimal DFA of any regular language is unique (up to isomorphism) can be found in introductory textbooks.

If the underlying task is to "read off" a regular expression from an automaton, don't guess & proof but rather build the expression algorithmically to save time.

Raphael
  • 73.4k
  • 31
  • 184
  • 406