Как работает преобразование эпсилон для преобразования NFA в DFA?

Question

Это NFA:

Вот две таблицы, которые я сделал для DFA, а затем моя попытка получить эквивалент DFA:

Проблема в том, чтоЭпсилон не учитывается, потому что я не знаю, как конвертировать при наличии стрелок эпсилона.

Answer 1

Чтобы учесть эпсилон-переходы, вы можете выполнить любое количество эпсилон-переходов до и после прочтения следующего символа. Таким образом, вы не только учитываете, куда можно пойти, когда читаете символ 0 (в качестве примера), но и учитываете, куда можно пойти, когда выполняете эпсилон-переходы до и после, например ε* 0 ε*.

* 1004. * Это означает, что когда вы начинаете с состояния {A} и читаете символ 0, вы можете перейти в следующие состояния:

A --0--> B
A --0--> B --ε--> C
A --0--> C
A --ε--> B --ε--> C --0--> C

А для чтения символа 1 вы можете перейти кследующие состояния:

A --1--> A
A --1--> A --ε--> B
A --1--> A --ε--> B --ε--> C
A --ε--> B --1--> B
A --ε--> B --1--> B --ε--> C
A --ε--> B --ε--> C --1--> C

Таким образом, в полученном DFA переход будет выглядеть следующим образом:

+-------+---------+---------+
| state |    0    |    1    |
+-------+---------+---------+
|  {A}  |  {B,C}  | {A,B,C} |
+-------+---------+---------+

Answer 2

Это эпсилон-NFA, просто преобразуйте эпсилон-NFA в эквивалентный NFA без эпсилон-переходов. Создайте таблицу, как вы делали бы при преобразовании NFA в DFA, и вместо того, чтобы просто проверять, куда это состояние идет с входом, сначала проверьте, куда оно может перейти с переходами epsilon, затем с вводом, а затем снова с переходом epsilon (это называется эпсилон-замыкание). Таким образом, вы будете иметь наборы состояний, которые вы достигнете своими входами. Единственное, что вам нужно сделать - это пометить любое состояние, которое может достичь конечного состояния, используя только эпсилон-переход в качестве конечных состояний. Затем вы можете создать NFA без эпсилон-переходов, а затем использовать свои знания для преобразования в DFA. Просто пример;В вашей таблице показано, что B имеет пустой набор для ввода 0, но на самом деле он может принять эпсилон-переход к C и принять 0 там, так что это фактически не пустой набор.