Como um NFA usa transições epsilon?

12

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

insira a descrição da imagem aqui

O que me confunde é o salto em .ϵq0

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

  • Se um for inserido, o sistema passa para e ?1q1q2

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

user3472798
fonte
2
Volte para as definições: um NFA aceita uma palavra se qualquer cálculo nele aceitar. Os NFAs não são, por si só, "algoritmos" no sentido em que os DFA são.
Raphael

Respostas:

10

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ê:ϵ

Se a string for , seus autômatos terminam em q 0 e q 1ϵq0q1

Se sua string for '0', será novamente em e q 1q0q1

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".q2q0q2q1q0q1

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 1ϵ0q0q1q20111ϵ00111

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

H_DANILO
fonte
7
"significa que você está automaticamente em ambos os estados" - não acho que seja uma intuição útil, isto é, representa o não determinismo de maneira errada.
Raphael
Por que isso representa errado? Bem, pela definição de delta no não-determinismo, você obtém um conjunto de estados em vez de apenas 1 corretamente? Isso pode significar apenas que você está nos dois estados.
H_DANILO 22/01
Promove a ideia de que máquinas não determinísticas "experimentam todas as soluções em paralelo". Não é isso que acontece, falando algoritmicamente. O não determinismo é um formalismo descritivo, não uma técnica algorítmica.
Raphael
Tentei colocá-lo em uma maneira compreensível, já que hes lutando para entender os princípios de não-determinismo de uma forma teórica
H_DANILO
@Raphael O que seria uma intuição mais útil, na sua opinião?
precisa saber é o seguinte
6

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 .q0q0q1q1

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 .q00q0q10q01q21q1q11

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+011101


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.ϵϵ

Rick Decker
fonte
-1

Eu tentei construir o DFA para este NFA

- conjunto de alfabeto

-states setQ

funcσ(Q×(ϵ))P(Q)

q0=q0

FQ,F={q0}

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

alfabeto - o mesmo

- estadosQ=P(Q)

O estado atual é RP(Q)

- fechamento epsilon retorna um conjunto de estados alcançáveis ​​em zero ou mais ϵ - conexões para cada r RE(R)ϵrR

-transitionsσ(R,a)=rRE(σ(r,a))

q0=E({q0})

F=P(Q)÷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. ϵq0=E({q0})={q0,q1}q1ϵ

2. 0σ({q0,q1},0)=E(σ(q0,0))E(σ(q1,0))={q0,q1}{}={q0,q1}0

at least {ϵ,0}L(M)

Thanks to David Richerby

OrangeFish
fonte
Thanks for thanking me but I don't really see how this answers the question. You haven't established what language the machine accepts and you haven't addressed any of the three bulletted questions.
David Richerby
1) when input is ϵ (empty string) , FSM state is {q0,q1} 2) when input is 0 or even 0 FSM state is {q0,q1} both of those subjects of initial questions, is not it?
OrangeFish