Como um NFA usa transições epsilon?

Na foto abaixo, estou tentando descobrir o que exatamente esse NFA está aceitando.

O que me confunde é o salto em .$\epsilon$$q_0$

• Se um for inserido, o sistema passa para e (o estado de aceitação)?$0$$q_0$ $q_1$

• Se um for inserido, o sistema passa para e ?$1$$q_1$$q_2$

• O sistema passa para (estado de aceitação), se nenhuma entrada for fornecida (sequência vazia)?$q_1$

Toda vez que você está em um estado que tem um transição, isso significa que você está automaticamente em ambos os Estados, para simplificar isso para você:$\epsilon$

Se a string for , seus autômatos terminam em q 0 e q $\epsilon$$q_0$$q_1$

Se sua string for '0', será novamente em e q $q_0$$q_1$

Se sua string for '1', será apenas em , porque se você olhar do ponto de q 0 , você terá uma transição de '1' para q 2 , mas também precisará observar se está em q 1 (se você estivesse em q 0, você também sempre esteve em q 1 ), então não há transição '1'; portanto, esse caminho alternativo simplesmente "morre".$q_2$$q_0$$q_2$$q_1$$q_0$$q_1$

Apenas observando esses casos, é fácil ver que seus autômatos aceitam , 0 ∗ e passando de q 0 a q 1 , a única maneira de atingir q 2 é 0 ∗ 11 ∗ 1 , portanto, isso retoma seus autômatos a ϵ , 0 ∗ , 0 ∗ 11 ∗$\epsilon$$0^*$$q_0$$q_1$$q_2$$0^*11^*1$$\epsilon$$0^*$$0^*11^*1$

Espero que isso tenha ajudado, se você tiver mais alguma dúvida, basta perguntar!

No estado sem ler nenhuma entrada, o NFA permanece em q 0 e (em um universo alternativo, se desejar) também se move para o estado q 1 . Isso é semelhante ao que aconteceria em uma NFA que tivesse duas transições para estados diferentes na entrada de um caractere. Em particular, seu NFA aceita a string vazia, pois em nenhuma entrada ele pode fazer uma transição para o estado de aceitação q 1 .$q_0$$q_0$$q_1$$q_1$

Continuando o seu exemplo, do estado vendo a entrada 0 , ele consumiria esse símbolo, permaneceria no estado q 0 (o loop) e também passaria ao estado q 1 , aceitando assim a entrada 0 . No estado q 0, lendo a entrada 1 , o NFA passaria para o estado q 2 . Também pode não consumir o 1 , mudar para o estado q 1 em outro universo e ficar preso lá (e não aceitar, pois não havia lido toda a entrada), pois não há transição de q 1 para 1 .$q_0$$0$$q_0$$q_1$$0$$q_0$$1$$q_2$$1$$q_1$$q_1$$1$

Veja se você pode se convencer de que a língua aceite por esta máquina é denotado pela expressão regular , ou seja, qualquer string que consiste de zero ou mais 0 s seguido por nada ou dois ou mais 1 s.$0^*+0^*11^*1$$0$$1$

By the way, há um algoritmo que leva um NFA com -Move e produz um NFA equivalente sem £ -Move, que eu espero que você vai aprender em breve.$\epsilon$$\epsilon$

Eu tentei construir o DFA para este NFA

- conjunto de alfabeto$\sum$

-states set$Q$

func$\sigma(Q\times (\sum \cup {\epsilon} )) \to P(Q)$

$q_0 = q_0$

$F \subseteq Q, F = \{q_0\}$

Como todo NFA possui DFA igual, vamos construir o DFA para esse dado NFA.$M'$

alfabeto - o mesmo

- estados$Q' = P(Q)$

O estado atual é $R \in P(Q)$

- fechamento epsilon retorna um conjunto de estados alcançáveis ​​em zero ou mais ϵ - conexões para cada r ∈ $E(R)$$\epsilon$$r \in R$

-transitions$\sigma'(R,a) = \bigcup_{r \in R} E(\sigma(r,a))$

$q'_{0} = E(\{q_0\})$

$F' = P(Q) \div F$

Alguns cálculos neste FSM

ϵ na entrada: q ′ 0 = E ( { q 0 } ) = { q 0 , q 1 } estado inicial inclui q 1 para que o FSM aceite$1.$ $\epsilon$$q'_{0} = E(\{q0\}) = \{q_0, q_1\}$$q_1$$\epsilon$

$2.$ $0*$$\sigma'(\{q_0, q_1\}, 0) = E(\sigma(q_0,0)) \cup E(\sigma(q_1,0)) = \{q_0, q_1\} \cup \{ \} = \{q_0, q_1\}$$0*$

at least $\{\epsilon, 0* \} \subset L (M')$

Thanks to David Richerby