Šajā sadaļā mēs apspriedīsim metodi, kā pārveidot NFA par līdzvērtīgu DFA. NFA gadījumā, kad pašreizējam stāvoklim tiek dota konkrēta ievade, iekārta pāriet uz vairākiem stāvokļiem. Tam var būt nulle, viena vai vairākas kustības noteiktā ievades simbolā. No otras puses, DFA, kad pašreizējam stāvoklim tiek dota konkrēta ievade, iekārta pāriet tikai uz vienu stāvokli. DFA ir tikai viena kustība uz dotā ievades simbola.
Pieņemsim, ka M = (Q, ∑, δ, q0, F) ir NFA, kas pieņem valodu L(M). Jābūt ekvivalentam DFA, kas apzīmēts ar M' = (Q', ∑', q0', δ', F'), lai L(M) = L(M').
Darbības, lai pārveidotu NFA par DFA:
1. darbība: Sākotnēji Q' = ϕ
2. darbība: Pievienojiet q0 no NFA pie Q'. Pēc tam atrodiet pārejas no šī sākuma stāvokļa.
3. darbība: Laukā Q' atrodiet iespējamo stāvokļu kopu katram ievades simbolam. Ja šī stāvokļu kopa nav Q', pievienojiet to Q'.
vlc lejupielādēt youtube video
4. darbība: Programmā DFA galīgais stāvoklis būs visi stāvokļi, kas satur F (NFA galīgie stāvokļi)
1. piemērs:
Konvertējiet doto NFA par DFA.
Risinājums: Dotajai pāreju diagrammai mēs vispirms izveidosim pāreju tabulu.
| Valsts | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1, Q2} | q1 |
| *q2 | q2 | {q1, Q2} |
Tagad mēs iegūsim δ' pāreju stāvoklim q0.
amiša patela
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
δ' pāreju stāvoklim q1 iegūst šādi:
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
δ' pāreju stāvoklim q2 iegūst šādi:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Tagad mēs iegūsim δ' pāreju uz [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] Stāvoklis [q1, q2] ir arī galīgais stāvoklis, jo tas satur gala stāvokli q2. Izveidotā DFA pārejas tabula būs šāda:
vesels skaitlis līdz virknei Java
| Valsts | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
Pārejas diagramma būs šāda:
Stāvokli q2 var novērst, jo q2 ir nesasniedzams stāvoklis.
2. piemērs:
Konvertējiet doto NFA par DFA.
Risinājums: Dotajai pāreju diagrammai mēs vispirms izveidosim pāreju tabulu.
java string Charat
| Valsts | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Tagad mēs iegūsim δ' pāreju stāvoklim q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] δ' pāreju stāvoklim q1 iegūst šādi:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Tagad mēs iegūsim δ' pāreju uz [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] Līdzīgi,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Tāpat kā dotajā NFA, q1 ir gala stāvoklis, tad DFA jebkurā vietā, kur pastāv q1, šis stāvoklis kļūst par galīgo stāvokli. Tādējādi DFA galīgie stāvokļi ir [q1] un [q0, q1]. Tāpēc gala stāvokļu kopa F = {[q1], [q0, q1]}.
apakšvirkne bash
Izveidotā DFA pārejas tabula būs šāda:
| Valsts | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
Pārejas diagramma būs šāda:
Pat mēs varam mainīt DFA stāvokļu nosaukumus.
Pieņemsim
A = [q0] B = [q1] C = [q0, q1]
Ar šiem jaunajiem nosaukumiem DFA būs šāds:
