Vantaggi / svantaggi di NFA su DFA e viceversa

Gli automi non deterministici possono avere molti meno stati, ma il motore per valutarli deve essere capace di essere in più stati contemporaneamente - tutti gli stati possibili. Ciò può comportare un compromesso tra i requisiti di memoria e la complessità del codice durante l'esecuzione dell'automa.

Personalmente, penso che i problemi più interessanti riguardino il modo in cui si manipolano gli stessi automi.

Un DFA può essere considerato un caso speciale NFA - IOW è possibile definire NFA per indicare potenzialmente (ma non necessariamente) non deterministico.

Anche con DFA, ci sono molti possibili automi equivalenti che daranno lo stesso comportamento. Ma c'è un solo minimo DFA con quel comportamento. Questo dà una forma canonica sia per una famiglia di DFA che per un (molto più grande) insieme di NFA. Ma anche quando si definisce la forma canonica per tutti gli NFA equivalenti, è necessario utilizzare un automa deterministico canonico minimo.

In termini di codifica, c'è molto di più nella definizione di un DFA canonico che in una semplice minimizzazione: è necessaria anche una rappresentazione canonica. Tuttavia, utilizzando normali algoritmi di minimizzazione, questi problemi tendono a risolversi nella mia esperienza, fondamentalmente perché il codice di minimizzazione è deterministico stesso.

Una volta che hai una forma canonica di un automa, puoi ricavare un hash o fare confronti ordinati: puoi usare gli automi come chiavi nelle strutture dati.

In teoria, tutti gli NFA hanno DFA equivalenti. In pratica, le informazioni extra codificate nel modello (al di fuori del linguaggio formale / teoria degli automi finiti) come le annotazioni sugli stati possono significare che alcuni NFA non hanno DFA equivalenti - sono intrinsecamente non deterministici. Nella mia esperienza, eliminando tutto il non-determinismo che può essere eliminato (con una variante della costruzione del sottoinsieme), combinato con alcune pulizie extra e minimizzazione, sembra ancora sufficiente dare forme canoniche, anche se non l'ho mai dimostrato formalmente.

Inoltre, non esiste un unico automa equivalente minimale - solo un automa equivalente deterministico (o as-deterministico-come-possibile con annotazioni di stato). Un NFA equivalente a DFA minimo potrebbe essere molto più piccolo, ma non esiste (in generale) un NFA equivalente più piccolo e unico.

Quindi lavorare con i DFA è allettante perché c'è sempre un risultato canonico ben definito. Se il tuo obiettivo sono piccoli automi, è bello avere una definizione chiara di "più piccolo" e sapere sempre che lo stai raggiungendo.

Usando gli NFA, perdi quella bella sensazione "questo-è-il-miglior-risultato". Devi accontentarti di "piccolo" anziché di "più piccolo". Potresti ottenere diversi automi in cui ti aspetti risultati equivalenti e non essere sicuro che siano equivalenti. Ma un tipico "piccolo" NFA può essere molto più piccolo del suo DFA equivalente "più piccolo", quindi il superlativo potrebbe essere una falsa pista.

Penso che sia un po 'come gli algoritmi di approssimazione. ho bisogno del risultato "perfetto"? Anche se in questo caso, il risultato NFA è ancora (in termini di comportamento) perfetto. Solo la rappresentazione perde l'etichetta "perfetta" e anche in questo caso, etichettare la DFA minima come "perfetta" funziona solo perché ignori le rappresentazioni NFA potenzialmente migliori.

Ad ogni modo, quando si lavora con gli NFA, la scelta delle rappresentazioni per i risultati è fondamentalmente euristica. Ci sono ovviamente metodi ben noti per manipolare gli NFA (l'approccio "derivate parziali delle espressioni regolari" è uno, sebbene non sia così familiare con questi me stesso - derivati dalle espressioni regolari (senza il "parziale" sono un metodo precedente per non- necessariamente DFA minimi).

I DFA sono allettanti perché puoi evitare quell'area grigia soggettiva. Ma sono abbastanza fiducioso che questa tentazione dovrebbe essere trattata con sospetto - perché anch'io sono caduto in questa trappola: - (

In tutta onestà, i DFA di cui mi occupo non sono così grandi. Ma avendo qualche migliaio di stati in cui intuitivamente mi aspettavo ci sono un sacco di volte, e questo non conta tutti gli stati generati e scartati per risultati intermedi. Sono sopravvissuto a questo relativamente incolume, ma con molto più rispetto per il termine "crescita esponenziale".

Il link offre una buona panoramica delle differenze tra NFA e DFA, oltre a informazioni concrete per come fare in modo che i DFA facciano cose che la maggior parte delle persone non pensa di poter fare (trova i limiti dei subpattern). La ragione per cui molte persone non sanno che è possibile è perché la maggior parte dei programmatori riceve le informazioni da Jeffrey Friedl, che ha sbagliato la teoria in un libro altrimenti meraviglioso sulle espressioni regolari. (Raccomando Mastering Regular Expressions perché è una buona introduzione pratica a loro, ma la teoria non è corretta.)

Se vuoi la versione semplice, le NFA sono più semplici da implementare e ti permettono di implementare più funzionalità, al costo di avere alcuni casi patologici in cui impiegheranno del tempo esponenziale per capire che non c'è corrispondenza. (In pratica, non combacerà prima che il Sole esploda.) Al contrario, i DFA offrono garanzie prestazionali, ma alcune espressioni regolari patologiche possono richiedere una quantità di memoria estremamente grande da esprimere come DFA.

È passato un po 'di tempo da quando ho preso la teoria di CS, ma credo che non ci sia alcuna differenza funzionale tra i due. Qualsiasi lingua che può essere definita in NFA può anche essere definita in DFA.

NFA è un po 'più complesso da implementare, ma una volta implementato, la creazione di grafici diventa più semplice per l'utente finale. In altre parole, per definire la stessa lingua utilizzando DFA, ti verrà richiesto di definire più stati e transizioni rispetto a quando utilizzi NFA.