Autômatos finitos não determinísticos

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, . $\epsilon$

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

Meu entendimento é que passará para que não é um estado de aceitação. $\epsilon$ $q_3$

regular-languages finite-automata nondeterminism Leopardo convexo
fonte

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?

ϵ

$\epsilon$

John L.

Obrigado pelos links abrangentes - acho que entendi isso agora.

Convex Leopard

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

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: $w$ $w$ $w$

q_{0} \overset{w_{1}}{\to} q_{1} \overset{w_{2}}{\to} q_{2} \overset{w_{3}}{\to} \dots \overset{w_{n}}{\to} q_{n}

$q_0 \stackrel{w_1}\to q_1 \stackrel{w_2}\to q_2 \stackrel{w_3}\to \cdots \stackrel{w_n}\to q_n$

$q_0$ é um estado inicial. (O modelo usual permite apenas um estado inicial, mas podemos relaxar esse requisito.)
$q_n$ é um estado final (também chamado de estado de aceitação).
Cada transição corresponde a uma transição da palavra NFA. $q_{i-1} \stackrel{w_i}\to q_i$
$w = w_1 \ldots w_n$ .

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. $\epsilon$ $\epsilon$

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 ). $\epsilon$

q_{0} \overset{ϵ}{\to} q_{1} \overset{ϵ}{\to} \dots \overset{ϵ}{\to} q_{n}

$q_0 \stackrel\epsilon\to q_1 \stackrel\epsilon\to \cdots \stackrel\epsilon\to q_n$

q_{0}

$q_0$

q_{n}

$q_n$

ϵ

$\epsilon$

n = 0

$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

ϵ

$\epsilon$

q 1 \to q 1

$q1 \rightarrow q1$

q 1 \to q 3

$q1 \rightarrow q3$

q 1 \to q 1

$q1 \rightarrow q1$

ϵ

$\epsilon$

Convex Leopard

Sim, é uma boa descrição.

Yuval Filmus

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

Respostas: