1. DFA: DFA fa referència a l'autòmat finit determinista. Es diu que un autòmat finit (FA) és determinista si correspon a un símbol d'entrada, hi ha un únic estat resultant, és a dir, només hi ha una transició. Un autòmat finit determinista és un conjunt de cinc tuples representades com,
On,
P: Un conjunt finit no buit d'estats en el control finit (qo, q1, q2, …).
Σ: Un conjunt finit no buit de símbols d'entrada.
δ: És una funció de transició que pren dos arguments, un estat i un símbol d'entrada, retorna un únic estat.
qo: és l'estat inicial, un dels estats de Q.
F: És un conjunt no buit d'estats finals/estats d'acceptació del conjunt pertanyent a Q.
2. CAUSES:
NFA fa referència a un autòmat finit no determinista. Es diu que un autòmat finit (FA) no és determinista si hi ha més d'una possible transició d'un estat al mateix símbol d'entrada.
Un autòmat finit no determinista també és un conjunt de cinc tuples i es representa com,
On,
P: Un conjunt d'estats finits no buits.
Σ: Un conjunt de símbols d'entrada finits no buits.
δ: és una funció de transició que pren un estat de Q i un símbol d'entrada de i retorna un subconjunt de Q.
qo: estat inicial de NFA i membre de Q.
F: Un conjunt no buit d'estats finals i membre de Q.
Requisit previ - Acabat automàtic
Diferència entre DFA i NFA:
| DFA | NFA |
|---|---|
| DFA són les sigles de Deterministic Finite Automata. | NFA significa autòmats finits no deterministes. |
| Per a cada representació simbòlica de l'alfabet, només hi ha una transició d'estat a DFA. | No cal especificar com reacciona la NFA segons algun símbol. |
| DFA no pot utilitzar la transició de cadena buida. | NFA pot utilitzar la transició de cadena buida. |
| DFA es pot entendre com una màquina. | NFA es pot entendre com diverses petites màquines que utilitzen al mateix temps. |
| A DFA, el següent estat possible s'estableix clarament. | A NFA, cada parell d'estat i símbol d'entrada pot tenir molts estats següents possibles. |
| DFA és més difícil de construir. | NFA és més fàcil de construir. |
| DFA rebutja la cadena en cas que acabi en un estat diferent de l'estat d'acceptació. | NFA rebutja la corda en cas que totes les branques moren o rebutgen la corda. |
| El temps necessari per executar una cadena d'entrada és menor. | El temps necessari per executar una cadena d'entrada és més. |
| Tots els DFA són NFA. | No tots els NFA són DFA. |
| DFA requereix més espai. | NFA requereix menys espai que DFA. |
| No es permet la configuració morta. Per exemple: si donem l'entrada com a 0 a l'estat q0, hem de donar 1 com a entrada a q0 com a bucle propi. | Es permet la configuració morta. Per exemple: si donem l'entrada com a 0 a l'estat q0, podem donar la següent entrada 1 a q1 que passarà al següent estat. |
| δ: QxΣ -> Q és a dir, el següent estat possible pertany a Q. | δ: Qx(Σ U ε) -> 2^Q és a dir, el següent estat possible pertany al conjunt de potències de Q. |
| La marxa enrere està permesa a DFA. | La marxa enrere no sempre és possible a NFA. |
| La conversió de l'expressió regular a DFA és difícil. | La conversió de l'expressió regular a NFA és més senzilla en comparació amb DFA. |
| El moviment Epsilon no està permès a DFA | El moviment d'Epsilon està permès a NFA |
| DFA només permet un moviment per a l'alfabet d'entrada única. | Hi pot haver elecció (més d'un moviment) per a l'alfabet d'entrada única. |