Un NFA pot tenir zero, un o més d'un moviment d'un estat donat en un símbol d'entrada donat. Un NFA també pot tenir moviments NULL (moviments sense símbol d'entrada). D'altra banda, DFA té un i només un moviment des d'un estat determinat en un símbol d'entrada determinat.

Passos per convertir NFA a DFA:

Pas 1: Converteix l'NFA donat a la seva taula de transició equivalent
Per convertir l'NFA a la seva taula de transició equivalent, hem d'enumerar tots els estats, els símbols d'entrada i les regles de transició. Les regles de transició es representen en forma de matriu, on les files representen l'estat actual, les columnes representen el símbol d'entrada i les cel·les representen l'estat següent.

Pas 2: creeu l'estat inicial de DFA
L'estat inicial del DFA és el conjunt de tots els estats inicials possibles al NFA. Aquest conjunt s'anomena tancament d'èpsilon de l'estat inicial de l'NFA. El tancament d'èpsilon és el conjunt de tots els estats que es poden assolir des de l'estat inicial seguint transicions èpsilons (?).

Pas 3: creeu la taula de transició de DFA
La taula de transició de la DFA és similar a la taula de transició de la NFA, però en lloc d'estats individuals, les files i columnes representen conjunts d'estats. Per a cada símbol d'entrada, la cel·la corresponent de la taula de transició conté el tancament d'èpsilons del conjunt d'estats obtinguts seguint les regles de transició de la taula de transicions de l'NFA.

Pas 4: creeu els estats finals de DFA
Els estats finals de la DFA són els conjunts d'estats que contenen almenys un estat final de la NFA.

Pas 5: simplifiqueu el DFA
El DFA obtingut als passos anteriors pot contenir estats i transicions innecessaris. Per simplificar el DFA, podem utilitzar les tècniques següents:

• Eliminar els estats inabastables: els estats als quals no es pot accedir des de l'estat inicial es poden eliminar del DFA.
• Elimina els estats morts: els estats que no poden conduir a un estat final es poden eliminar del DFA.
• Fusionar estats equivalents: els estats que tenen les mateixes regles de transició per a tots els símbols d'entrada es poden fusionar en un sol estat.

Pas 6: repetiu els passos 3-5 fins que no sigui possible més simplificació
Després de simplificar el DFA, repetim els passos 3-5 fins que no sigui possible més simplificació. El DFA final obtingut és el DFA minimitzat equivalent al NFA donat.

Exemple: Considereu el següent NFA que es mostra a la figura 1.

A continuació es mostren els diferents paràmetres per a NFA. Q = { q0, q1, q2 } ? = ( a, b ) F = { q2 } ? (Funció de transició de NFA)

Pas 1: Q’ = ? Pas 2: Q' = {q0} Pas 3: per a cada estat de Q', troba els estats per a cada símbol d'entrada. Actualment, l'estat a Q' és q0, trobeu els moviments de q0 al símbol d'entrada a i b mitjançant la funció de transició de NFA i actualitzeu la taula de transició de DFA. ?’ (Funció de transició de DFA)

Ara { q0, q1 } es considerarà com un estat únic. Com que la seva entrada no és a Q', afegiu-la a Q'. Així, Q' = { q0, { q0, q1 } } Ara, els moviments de l'estat { q0, q1 } en diferents símbols d'entrada no estan presents a la taula de transició de DFA, ho calcularem com: ( { q0, q1 } , a ) = ? ( q0, a ) ? ? ( q1, a ) = { q0, q1 } ?’ ( { q0, q1 }, b ) = ? ( q0, b ) ? ? ( q1, b ) = { q0, q2 } Ara actualitzarem la taula de transició de DFA. ?’ (Funció de transició de DFA)

Ara { q0, q2 } es considerarà com un estat únic. Com que la seva entrada no està a Q', afegiu-la a Q'. Així, Q' = { q0, { q0, q1 }, { q0, q2 } } Ara, els moviments de l'estat {q0, q2} a diferents símbols d'entrada no estan presents a la taula de transició de DFA, ho calcularem com: ?' ( { q0, q2 }, a ) = ? ( q0, a ) ? ? ( q2, a ) = { q0, q1 } ?’ ( { q0, q2 }, b ) = ? ( q0, b ) ? ? ( q2, b ) = { q0 } Ara actualitzarem la taula de transició de DFA. ?’ (Funció de transició de DFA)

Com que no es genera cap nou estat, hem acabat amb la conversió. L'estat final de DFA serà l'estat que tingui q2 com a component, és a dir, { q0, q2 } A continuació es mostren els diferents paràmetres per a DFA. Q’ = { q0, { q0, q1 }, { q0, q2 } } ? = ( a, b ) F = { { q0, q2 } } i funció de transició ?’ com es mostra més amunt. El DFA final de l'NFA anterior s'ha mostrat a la figura 2.

Nota : De vegades, no és fàcil convertir l'expressió regular a DFA. Primer podeu convertir l'expressió regular a NFA i després NFA a DFA.

Pregunta: El nombre d'estats de l'autòmat finit determinista mínim corresponent a l'expressió regular (0 + 1)* (10) és ____________.

Solució : Primer, farem un NFA per a l'expressió anterior. Per fer un NFA per a (0 + 1)*, NFA estarà en el mateix estat q0 al símbol d'entrada 0 o 1. Aleshores, per a la concatenació, afegirem dos moviments (q0 a q1 per a 1 i q1 a q2 per a 0) tal com es mostra. a la figura 3.

Aquest article ha estat contribuït per Sonal Tuteja.