I denne delen vil vi diskutere metoden for å konvertere NFA til tilsvarende DFA. I NFA, når en spesifikk inngang er gitt til gjeldende tilstand, går maskinen til flere tilstander. Den kan ha null, ett eller flere trekk på et gitt inngangssymbol. På den annen side, i DFA, når en spesifikk inngang er gitt til den nåværende tilstanden, går maskinen til bare én tilstand. DFA har bare ett trekk på et gitt inngangssymbol.
SIM-kort satt inn men ingen tjeneste android
La, M = (Q, ∑, δ, q0, F) er en NFA som aksepterer språket L(M). Det skal være ekvivalent DFA betegnet med M' = (Q', ∑', q0', δ', F'), slik at L(M) = L(M').
Trinn for å konvertere NFA til DFA:
Trinn 1: Opprinnelig Q' = ϕ
Steg 2: Legg til q0 av NFA til Q'. Finn deretter overgangene fra denne starttilstanden.
Trinn 3: I Q', finn det mulige settet med tilstander for hvert inngangssymbol. Hvis dette settet med tilstander ikke er i Q', så legg det til Q'.
Trinn 4: I DFA vil den endelige tilstanden være alle statene som inneholder F (slutttilstander for NFA)
Eksempel 1:
Konverter den gitte NFA til DFA.
Løsning: For det gitte overgangsdiagrammet vil vi først konstruere overgangstabellen.
| Stat | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1, q2} | q1 |
| *q2 | q2 | {q1, q2} |
Nå vil vi få δ'-overgang for tilstand q0.
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
δ'-overgangen for tilstand q1 oppnås som:
år inn i kvartaler
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
δ'-overgangen for tilstand q2 oppnås som:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Nå vil vi få δ'-overgang på [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] Tilstanden [q1, q2] er også den endelige tilstanden fordi den inneholder en slutttilstand q2. Overgangstabellen for den konstruerte DFAen vil være:
| Stat | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
Overgangsdiagrammet vil være:
Tilstanden q2 kan elimineres fordi q2 er en uoppnåelig tilstand.
Eksempel 2:
Konverter den gitte NFA til DFA.
Løsning: For det gitte overgangsdiagrammet vil vi først konstruere overgangstabellen.
et eksempel på et åpen kildekode-os er
| Stat | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Nå vil vi få δ'-overgang for tilstand q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] δ'-overgangen for tilstand q1 oppnås som:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Nå vil vi få δ'-overgang på [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] På samme måte,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Som i den gitte NFA er q1 en endelig tilstand, så i DFA uansett hvor q1 eksisterer blir den tilstanden en endelig tilstand. Derfor i DFA er slutttilstander [q1] og [q0, q1]. Derfor sett med slutttilstander F = {[q1], [q0, q1]}.
10 av 50
Overgangstabellen for den konstruerte DFAen vil være:
| Stat | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
Overgangsdiagrammet vil være:
Selv vi kan endre navnet på statene i DFA.
Anta
A = [q0] B = [q1] C = [q0, q1]
Med disse nye navnene vil DFA være som følger:
