Na foto abaixo, estou tentando descobrir o que exatamente esse NFA está aceitando.
O que me confunde é o salto em .ϵϵq0q0
Se um for inserido, o sistema passa para e (o estado de aceitação)?00q0q0 q1q1
Se um for inserido, o sistema passa para e ?11q1q1q2q2
O sistema passa para (estado de aceitação), se nenhuma entrada for fornecida (sequência vazia)?q1q1
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.
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ϵϵq0q0q1q1
Se sua string for '0', será novamente em e q 1q0q0q1q1
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".q2q2q0q0q2q2q1q1q0q0q1q1
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ϵϵ0∗0∗q0q0q1q1q2q20∗11∗10∗11∗1ϵϵ0∗0∗0∗11∗10∗11∗1
Espero que isso tenha ajudado, se você tiver mais alguma dúvida, basta perguntar!
"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.
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.
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
@Raphael O que seria uma intuição mais útil, na sua opinião?
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 .q0q0q0q0q1q1q1q1
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 .q0q000q0q0q1q100q0q011q2q211q1q1q1q111
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∗10∗+0∗11∗10011
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.ϵϵϵϵ
Eu tentei construir o DFA para este NFA
- conjunto de alfabeto∑∑
-states setQQ
funcσ(Q×(∑∪ϵ))→P(Q)σ(Q×(∑∪ϵ))→P(Q)
Como todo NFA possui DFA igual, vamos construir o DFA para esse dado NFA.M′M′
O estado atual é R∈P(Q)R∈P(Q)
- fechamento epsilon retorna um conjunto de estados alcançáveis ​​em zero ou mais ϵ - conexões para cada r ∈ RE(R)E(R)ϵϵr∈Rr∈R
-transitionsσ′(R,a)=⋃r∈RE(σ(r,a))σ′(R,a)=⋃r∈RE(σ(r,a))
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.
1) when input is ϵϵ (empty string) , FSM state is {q0,q1}{q0,q1} 2) when input is 00 or even 0∗0∗ FSM state is {q0,q1}{q0,q1} both of those subjects of initial questions, is not it?