Skip to main content
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
Source Link

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 algorithmicallyalgorithmically to save time.

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.

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.

Source Link
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.