En aquesta secció, parlarem del mètode per convertir NFA al seu DFA equivalent. A NFA, quan es dóna una entrada específica a l'estat actual, la màquina passa a diversos estats. Pot tenir zero, un o més d'un moviment en un símbol d'entrada donat. D'altra banda, a DFA, quan es dóna una entrada específica a l'estat actual, la màquina només passa a un estat. DFA només té un moviment en un símbol d'entrada determinat.
Sigui, M = (Q, ∑, δ, q0, F) és un NFA que accepta el llenguatge L(M). Hi hauria d'haver un DFA equivalent denotat per M' = (Q', ∑', q0', δ', F') de manera que L(M) = L(M').
Passos per convertir NFA a DFA:
Pas 1: Inicialment Q' = ϕ
Pas 2: Afegiu q0 de NFA a Q'. A continuació, trobeu les transicions d'aquest estat inicial.
Pas 3: A Q', trobeu el conjunt possible d'estats per a cada símbol d'entrada. Si aquest conjunt d'estats no es troba a Q', afegiu-lo a Q'.
programació cobol
Pas 4: A DFA, l'estat final seran tots els estats que continguin F (estats finals de NFA)
Exemple 1:
Converteix l'NFA donat a DFA.
Solució: Per al diagrama de transició donat, primer construirem la taula de transicions.
| Estat | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1, q2} | q1 |
| *q2 | q2 | {q1, q2} |
Ara obtindrem la transició δ' per a l'estat q0.
b més arbre
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
La transició δ' per a l'estat q1 s'obté com:
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
La transició δ' per a l'estat q2 s'obté com:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Ara obtindrem la transició δ' a [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] L'estat [q1, q2] també és l'estat final perquè conté un estat final q2. La taula de transició per al DFA construït serà:
exemple de mapa java
| Estat | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
El diagrama de transició serà:
L'estat q2 es pot eliminar perquè q2 és un estat inabastable.
Exemple 2:
Converteix l'NFA donat a DFA.
Solució: Per al diagrama de transició donat, primer construirem la taula de transicions.
subcadena del mètode java
| Estat | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Ara obtindrem la transició δ' per a l'estat q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] La transició δ' per a l'estat q1 s'obté com:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Ara obtindrem la transició δ' a [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] De la mateixa manera,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Com en l'NFA donat, q1 és un estat final, aleshores a DFA on hi hagi q1 aquest estat es converteix en un estat final. Per tant, al DFA, els estats finals són [q1] i [q0, q1]. Per tant, conjunt d'estats finals F = {[q1], [q0, q1]}.
punter de desreferència c
La taula de transició per al DFA construït serà:
| Estat | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
El diagrama de transició serà:
Fins i tot podem canviar el nom dels estats de DFA.
Suposem
A = [q0] B = [q1] C = [q0, q1]
Amb aquests nous noms, el DFA serà el següent:
