In questa sezione discuteremo il metodo per convertire NFA nel suo DFA equivalente. In NFA, quando viene fornito un input specifico allo stato corrente, la macchina passa a più stati. Può avere zero, una o più mosse su un dato simbolo di input. D'altra parte, in DFA, quando viene fornito un input specifico allo stato corrente, la macchina passa a un solo stato. DFA ha una sola mossa su un dato simbolo di input.
Sia M = (Q, ∑, δ, q0, F) un NFA che accetta il linguaggio L(M). Dovrebbe esserci un DFA equivalente indicato con M' = (Q', ∑', q0', δ', F') tale che L(M) = L(M').
Passaggi per convertire NFA in DFA:
Passo 1: Inizialmente Q' = ϕ
Passo 2: Aggiungere q0 di NFA a Q'. Quindi trova le transizioni da questo stato iniziale.
Passaggio 3: In Q', trova il possibile insieme di stati per ciascun simbolo di input. Se questo insieme di stati non è in Q', aggiungilo a Q'.
coda di priorità Java
Passaggio 4: In DFA, lo stato finale saranno tutti gli stati che contengono F (stati finali di NFA)
Esempio 1:
Converti il dato NFA in DFA.
Soluzione: Per il diagramma di transizione dato costruiremo prima la tabella di transizione.
| Stato | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1, q2} | q1 |
| *q2 | q2 | {q1, q2} |
Ora otterremo la transizione δ' per lo stato q0.
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
La transizione δ' per lo stato q1 si ottiene come:
javac non è riconosciuto
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
La transizione δ' per lo stato q2 si ottiene come:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Ora otterremo la transizione δ' su [q1, q2].
δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0) = {q1, q2} ∪ {q2} = [q1, q2] δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1) = {q1} ∪ {q1, q2} = {q1, q2} = [q1, q2] Anche lo stato [q1, q2] è lo stato finale perché contiene uno stato finale q2. La tabella di transizione per il DFA costruito sarà:
| Stato | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
Il diagramma di transizione sarà:
Lo stato q2 può essere eliminato perché q2 è uno stato irraggiungibile.
differenza tra azienda e azienda
Esempio 2:
Converti il dato NFA in DFA.
Soluzione: Per il diagramma di transizione dato costruiremo prima la tabella di transizione.
| Stato | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Ora otterremo la transizione δ' per lo stato q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] La transizione δ' per lo stato q1 si ottiene come:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Ora otterremo la transizione δ' su [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] Allo stesso modo,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Come nel dato NFA, q1 è uno stato finale, quindi in DFA ovunque esista q1 quello stato diventa uno stato finale. Quindi nel DFA gli stati finali sono [q1] e [q0, q1]. Quindi insieme degli stati finali F = {[q1], [q0, q1]}.
applet
La tabella di transizione per il DFA costruito sarà:
| Stato | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
Il diagramma di transizione sarà:
Anche noi possiamo cambiare il nome degli stati del DFA.
Supponiamo
A = [q0] B = [q1] C = [q0, q1]
Con queste nuove denominazioni il DFA sarà il seguente:
