Autômatos finitos não determinísticos | Sipser Exemplo 1.16

9

Estou trabalhando no livro Sipser (2ª edição) e me deparei com este exemplo, que não entendo. No livro, afirma que esse NFA aceita a string vazia, .ϵ

Alguém poderia me explicar por que esse é o caso?

Meu entendimento é que passará para que não é um estado de aceitação.ϵq3

insira a descrição da imagem aqui

Leopardo convexo
fonte
11
Essa é uma pergunta clássica sobre o uso do em uma NFA. Aqui está uma pergunta sobre o mesmo exemplo, o que significa uma sequência de entrada de epsilon? . Há também a questão do significado de ε em NFA-ε? e como um NFA usa transições epsilon? ϵ
John L.
Obrigado pelos links abrangentes - acho que entendi isso agora.
Convex Leopard

Respostas:

10

Você está confundindo com uma carta. Não é uma carta! É apenas a corda vazia.ϵ

Vamos considerar um modelo um pouco mais geral, "word-NFA". Uma palavra-NFA é como uma NFA, mas cada transição é rotulada com uma palavra arbitrária. Dizemos que a palavra NFA aceita uma palavra se houver uma caminhada de um estado inicial para um estado final, de modo que, se concatenarmos os rótulos das arestas na caminhada, obteremos . Nos símbolos, uma palavra NFA aceita se houver uma sequência de transições de tal modo que:www

q0w1q1w2q2w3wnqn

  1. q0 é um estado inicial. (O modelo usual permite apenas um estado inicial, mas podemos relaxar esse requisito.)
  2. qn é um estado final (também chamado de estado de aceitação).
  3. Cada transição corresponde a uma transição da palavra NFA.qi1wiqi
  4. w=w1wn .

Um NFA é uma palavra-NFA na qual todas as transições são rotuladas por letras (ou seja, palavras com tamanho exatamente 1), e um -NFA é aquele em que todas as transições são rotuladas por letras ou (ou seja, palavras com comprimento no máximo 1). Normalmente, também exigimos que exista um estado inicial único.ϵϵ

Uma palavra-NFA aceita se houver uma sequência de transições modo que seja um estado inicial, seja um estado final , e todas as transições são válidas. Em particular, se algum estado for inicial e final, a palavra NFA aceita (isso corresponde a ).ϵ

q0ϵq1ϵϵqn
q0qnϵn=0

Yuval Filmus
fonte
AHA, obrigado, isso faz sentido agora. Tão intuitivamente, quando obtemos , temos dois "ramos": e . Desde é um estado aceito, aceitamosϵq1q1 1q1q3q1q1ϵ
Convex Leopard
11
Sim, é uma boa descrição.
Yuval Filmus