În această secțiune, vom discuta despre metoda de conversie a NFA în DFA echivalent. În NFA, atunci când o anumită intrare este dată stării curente, mașina trece în mai multe stări. Poate avea zero, una sau mai multe mișcări pe un simbol de intrare dat. Pe de altă parte, în DFA, atunci când o anumită intrare este dată stării curente, mașina trece la o singură stare. DFA are o singură mișcare pe un simbol de intrare dat.
Fie, M = (Q, ∑, δ, q0, F) este un NFA care acceptă limbajul L(M). Ar trebui să existe DFA echivalent notat cu M' = (Q', ∑', q0', δ', F') astfel încât L(M) = L(M').
Pași pentru conversia NFA în DFA:
Pasul 1: Inițial Q' = ϕ
Pasul 2: Adăugați q0 din NFA la Q'. Apoi găsiți tranzițiile de la această stare de început.
t flip flop
Pasul 3: În Q', găsiți setul posibil de stări pentru fiecare simbol de intrare. Dacă acest set de stări nu este în Q', atunci adăugați-l la Q'.
Pasul 4: În DFA, starea finală va fi toate stările care conțin F(stări finale ale NFA)
Exemplul 1:
Convertiți NFA dat în DFA.
Soluţie: Pentru diagrama de tranziție dată vom construi mai întâi tabelul de tranziție.
| Stat | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1, q2} | q1 |
| *q2 | q2 | {q1, q2} |
Acum vom obține tranziția δ' pentru starea q0.
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
Tranziția δ' pentru starea q1 se obține astfel:
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
Tranziția δ' pentru starea q2 se obține astfel:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Acum vom obține tranziția δ' pe [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] Starea [q1, q2] este și starea finală, deoarece conține o stare finală q2. Tabelul de tranziție pentru DFA construit va fi:
| Stat | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
Diagrama de tranziție va fi:
Starea q2 poate fi eliminată deoarece q2 este o stare de neatins.
Exemplul 2:
Convertiți NFA dat în DFA.
Soluţie: Pentru diagrama de tranziție dată vom construi mai întâi tabelul de tranziție.
| Stat | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Acum vom obține tranziția δ' pentru starea q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] Tranziția δ' pentru starea q1 se obține astfel:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Acum vom obține tranziția δ' pe [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] În mod similar,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Ca și în NFA dat, q1 este o stare finală, apoi în DFA oriunde există q1 acea stare devine o stare finală. Prin urmare, în DFA, stările finale sunt [q1] și [q0, q1]. Prin urmare, mulțime de stări finale F = {[q1], [q0, q1]}.
Tabelul de tranziție pentru DFA construit va fi:
| Stat | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
Diagrama de tranziție va fi:
Chiar și noi putem schimba numele statelor DFA.
factorial în c
Presupune
A = [q0] B = [q1] C = [q0, q1]
Cu aceste noi nume, DFA va fi după cum urmează:
