Un NFA può avere zero, una o più mosse da un dato stato su un dato simbolo di input. Un NFA può anche avere mosse NULL (mosse senza simbolo di input). D'altra parte, DFA ha una ed una sola mossa da un dato stato su un dato simbolo di input.

Passaggi per convertire NFA in DFA:

Passaggio 1: convertire l'NFA specificato nella tabella di transizione equivalente
Per convertire l'NFA nella sua tabella di transizione equivalente, dobbiamo elencare tutti gli stati, i simboli di input e le regole di transizione. Le regole di transizione sono rappresentate sotto forma di matrice, dove le righe rappresentano lo stato corrente, le colonne rappresentano il simbolo di input e le celle rappresentano lo stato successivo.

Passaggio 2: crea lo stato iniziale del DFA
Lo stato iniziale del DFA è l’insieme di tutti i possibili stati iniziali nell’NFA. Questo insieme è chiamato chiusura epsilon dello stato iniziale dell’NFA. La chiusura epsilon è l'insieme di tutti gli stati che possono essere raggiunti dallo stato iniziale seguendo le transizioni epsilon (?).

coda di priorità Java

Passaggio 3: crea la tabella di transizione del DFA
La tabella di transizione del DFA è simile alla tabella di transizione dell’NFA, ma invece dei singoli stati, le righe e le colonne rappresentano insiemi di stati. Per ciascun simbolo di input, la cella corrispondente nella tabella di transizione contiene la chiusura epsilon dell'insieme di stati ottenuti seguendo le regole di transizione nella tabella di transizione dell'NFA.

Passaggio 4: crea gli stati finali del DFA
Gli stati finali del DFA sono gli insiemi di stati che contengono almeno uno stato finale dell’NFA.

Passaggio 5: semplificare il DFA
Il DFA ottenuto nei passaggi precedenti potrebbe contenere stati e transizioni non necessari. Per semplificare il DFA possiamo utilizzare le seguenti tecniche:

javac non è riconosciuto

• Rimuovi stati irraggiungibili: gli stati che non possono essere raggiunti dallo stato iniziale possono essere rimossi dal DFA.
• Rimuovi stati morti: gli stati che non possono portare a uno stato finale possono essere rimossi dal DFA.
• Unisci stati equivalenti: gli stati che hanno le stesse regole di transizione per tutti i simboli di input possono essere uniti in un unico stato.

Passaggio 6: ripetere i passaggi 3-5 finché non è più possibile alcuna ulteriore semplificazione
Dopo aver semplificato il DFA, ripetiamo i passaggi 3-5 finché non sarà più possibile alcuna ulteriore semplificazione. Il DFA finale ottenuto è il DFA minimizzato equivalente al NFA fornito.

Esempio: Considerare il seguente NFA mostrato nella Figura 1.

Di seguito sono riportati i vari parametri per NFA. Q = { q0, q1, q2 } ? = ( a, b ) F = { q2 } ? (Funzione di transizione della NFA)

differenza tra azienda e azienda

Passaggio 1: Q’ = ? Passaggio 2: Q’ = {q0} Passaggio 3: Per ogni stato in Q’, trova gli stati per ciascun simbolo di input. Attualmente, lo stato in Q' è q0, trova le mosse da q0 sul simbolo di input a e b utilizzando la funzione di transizione di NFA e aggiorna la tabella di transizione di DFA. ?’ (Funzione di transizione del DFA)

Ora {q0, q1} sarà considerato come un unico stato. Poiché la sua voce non è in Q’, aggiungila a Q’. Quindi Q' = { q0, { q0, q1 } } Ora, i movimenti dallo stato { q0, q1 } su diversi simboli di input non sono presenti nella tabella di transizione di DFA, lo calcoleremo come: ?' ( { q0, q1 } , a ) = ? (q0, a)? ? ( q1, a ) = { q0, q1 } ?’ ( { q0, q1 }, b ) = ? (q0, b)? ? ( q1, b ) = { q0, q2 } Ora aggiorneremo la tabella di transizione di DFA. ?’ (Funzione di transizione del DFA)

Ora {q0, q2} sarà considerato come un unico stato. Poiché la sua voce non è in Q’, aggiungila a Q’. Quindi Q' = { q0, { q0, q1 }, { q0, q2 } } Ora, i movimenti dallo stato {q0, q2} su diversi simboli di input non sono presenti nella tabella di transizione di DFA, lo calcoleremo come: ?' ( { q0, q2 }, a ) = ? (q0, a)? ? ( q2, a ) = { q0, q1 } ?’ ( { q0, q2 }, b ) = ? (q0, b)? ? ( q2, b ) = { q0 } Ora aggiorneremo la tabella di transizione di DFA. ?’ (Funzione di transizione del DFA)

Poiché non viene generato un nuovo stato, la conversione è terminata. Lo stato finale del DFA sarà lo stato che ha q2 come componente, ovvero { q0, q2 } Di seguito sono riportati i vari parametri per DFA. Q' = { q0, { q0, q1 }, { q0, q2 } } ? = ( a, b ) F = { { q0, q2 } } e la funzione di transizione ?’ come mostrato sopra. Il DFA finale per l'NFA sopra è stato mostrato nella Figura 2.

Nota : A volte non è facile convertire l'espressione regolare in DFA. Innanzitutto puoi convertire l'espressione regolare in NFA e poi NFA in DFA.

Domanda : Il numero di stati nell'automa finito deterministico minimo corrispondente all'espressione regolare (0 + 1)* (10) è ____________.

Soluzione: Per prima cosa creeremo un NFA per l'espressione di cui sopra. Per creare un NFA per (0 + 1)*, NFA sarà nello stesso stato q0 sul simbolo di input 0 o 1. Quindi per la concatenazione, aggiungeremo due mosse (da q0 a q1 per 1 e da q1 a q2 per 0) come mostrato nella Figura 3.

applet

Questo articolo è stato contribuito da Sonal Tuteja.