Epsilon Transizioni in un NFA

Question

Epsilon Transizioni in un NFA

#1 da (2 voti)

3

Sto tentando di insegnarmi le basi degli automi finiti e ho esplorato le differenze tra gli automi definiti deterministici e l'auto finita non deterministica.

Una cosa che appare abbastanza spesso negli esempi on-line, diapositive delle lezioni e video di vari istruttori CS è la transizione epsilon. Il problema è che nessuno di loro fa un ottimo lavoro nello spiegare le transizioni epsilon. Semplicemente li fanno uscire dal nulla come questa misteriosa proprietà che ti permette di saltare da uno stato all'altro senza leggere un carattere di input.

O.K. Lo capisco, ma in che modo questi salti arbitrari sono facilitati semanticamente se dovessimo creare questo automa? Prendi l'immagine qui sotto per esempio. Diciamo che siamo in S0, ci sono due transizioni epsilon a s1 e s4. Come è deciso quale andare giù. Se vai su S1 e non hai un a, puoi tornare indietro e provare b? Dico questo perché le frecce non sembrano dedurre questo. O ho concepito questo errore, gli automi potrebbero effettivamente essere in entrambi gli stati S1 e S2 contemporaneamente?

Anche s3 e s6, hai transizioni epsilon a s7, quindi perché non abbiamo due stati di accettazione S3 e s4 invece?

Infine l'S2, ha due percorsi che reagiscono ad a, s5 ha due percorsi che reagiscono a b. Come funziona in pratica. Come viene determinato il percorso da seguire?

Quando rispondi cerca di limitare l'uso della matematica esoterica, e se usi operatori e simboli, spiegali chiaramente. Non sono un esperto di matematica.

theory

posta Andrew S 15.03.2014 - 09:12

fonte

1 risposta

Leggi altre domande sui tag theory

Creazione di un sistema di gestione magazzino / magazzino, con più posizioni per ciascun articolo Dove dovrebbe andare la logica dei dati CMS

score 2 · Accepted Answer

Poiché alcune idee sono già emerse nei commenti alla domanda, cerco di raccogliere queste idee in una risposta.

Penso che la tua principale fonte di confusione sia che cerchi di trattare un automa finito non deterministico come deterministico. Le transizioni epsilon dallo stato s0 indicano che da s0 puoi passare a {s1, s4} , ad esempio a un insieme che contiene entrambi gli stati contemporaneamente. L'ambiguità "Posso passare da s0 a s1 e da s0 a s2, quale dovrei prendere?" è risolto prendendo entrambi allo stesso tempo. Per essere più precisi, la transizione epsilon ti dice che s0 , s1 e s2 sono fondamentalmente lo stesso stato: essendo in s0 sei già in s1 e in s2 in modo da poter passare a uno di essi senza leggere alcun simbolo dall'input.

Allo stesso modo, puoi avere un'ambiguità se hai due transizioni da uno stato a stati diversi sullo stesso simbolo, come per s2 e a nell'esempio. In questo caso, quando è in stato s2 , se leggi il simbolo a vai a {s2, s3} . Cosa significa essere nello stato {s2, s3} ? Significa che da qui puoi applicare sia s2 -transitions che s3 -transitions.

Puoi sempre trasformare un NFA in un DFA equivalente dove gli stati in DFA corrispondono a un insieme di stati nell'NFA originale (applicando il costruzione powerset ).

L'esecuzione diretta di un NFA richiederebbe il backtracking durante l'esecuzione del DFA corrispondente è come eseguire tutti i diversi rami dell'NFA in parallelo (non è necessario alcun backtracking): la costruzione del powerset piega tutti i rami paralleli e rimuove le ambiguità.