Являются ли RE и конечные автоматы одинаковыми?

Question

Я хочу понять, если RE a ∗ ba ∗ ab ∗ такой же, как следующие конечные автоматы. Часть, в которой я запутался, состоит в том, что из состояния 3 в состояние 4 существует a b, что означает, что в конце языка должен быть b, а в RE просто b *, что означает 0 или более b. Если нет, что является правильным конечным автоматом для этого RE?

Answer 1

Действительно, регулярное выражение a*ba*ab* не эквивалентно DFA, показанному именно по той причине, которую вы указали в своем вопросе.

Алгоритм Томпсона - это стандартный способ систематического преобразования регулярного выражения в NFA. (Если вам нужен конечный автомат для детерминированности, вы можете запустить конструкцию подмножества .)