Autómata finito no determinista
En NDFA, para un símbolo de entrada particular, la máquina puede moverse a cualquier combinación de estados en la máquina. En otras palabras, no se puede determinar el estado exacto al que se mueve la máquina. Por lo tanto, se llamaNon-deterministic Automaton. Como tiene un número finito de estados, la máquina se llamaNon-deterministic Finite Machine o Non-deterministic Finite Automaton.
Definición formal de un NDFA
Un NDFA se puede representar por una tupla de 5 (Q, ∑, δ, q 0 , F) donde -
Q es un conjunto finito de estados.
∑ es un conjunto finito de símbolos llamados alfabetos.
δes la función de transición donde δ: Q × ∑ → 2 Q
(Aquí se ha tomado el conjunto de potencias de Q (2 Q ) porque en el caso de NDFA, de un estado, puede ocurrir una transición a cualquier combinación de estados Q)
q0es el estado inicial desde donde se procesa cualquier entrada (q 0 ∈ Q).
F es un conjunto de estados finales de Q (F ⊆ Q).
Representación gráfica de un NDFA: (igual que DFA)
Un NDFA está representado por dígrafos llamados diagrama de estado.
- Los vértices representan los estados.
- Los arcos etiquetados con un alfabeto de entrada muestran las transiciones.
- El estado inicial se denota por un solo arco entrante vacío.
- El estado final está indicado por círculos dobles.
Example
Sea un autómata finito no determinista →
- Q = {a, b, c}
- ∑ = {0, 1}
- q 0 = {a}
- F = {c}
La función de transición δ como se muestra a continuación:
| Estado actual | Siguiente estado para la entrada 0 | Siguiente estado para la entrada 1 |
|---|---|---|
| un | a, b | segundo |
| segundo | C | a, c |
| C | antes de Cristo | C |
Su representación gráfica sería la siguiente:
DFA frente a NDFA
La siguiente tabla enumera las diferencias entre DFA y NDFA.
| DFA | NDFA |
|---|---|
| La transición de un estado es a un único estado siguiente en particular para cada símbolo de entrada. Por eso se llama determinista . | La transición de un estado puede ser a varios estados siguientes para cada símbolo de entrada. Por eso se llama no determinista . |
| Las transiciones de cadenas vacías no se ven en DFA. | NDFA permite transiciones de cadenas vacías. |
| El retroceso está permitido en DFA | En NDFA, el retroceso no siempre es posible. |
| Requiere más espacio. | Requiere menos espacio. |
| Un DFA acepta una cadena si pasa a un estado final. | Una cadena es aceptada por un NDFA, si al menos una de todas las posibles transiciones termina en un estado final. |
Aceptadores, clasificadores y transductores
Aceptador (reconocedor)
Un autómata que calcula una función booleana se llama acceptor. Todos los estados de un aceptador son aceptar o rechazar las entradas que se le dan.
Clasificador
UN classifier tiene más de dos estados finales y da una única salida cuando termina.
Transductor
Un autómata que produce salidas basadas en la entrada actual y / o el estado anterior se llama transducer. Los transductores pueden ser de dos tipos:
Mealy Machine - La salida depende tanto del estado actual como de la entrada actual.
Moore Machine - La salida depende solo del estado actual.
Aceptabilidad por DFA y NDFA
Una cadena es aceptada por un DFA / NDFA si el DFA / NDFA que comienza en el estado inicial termina en un estado de aceptación (cualquiera de los estados finales) después de leer la cadena por completo.
Una cadena S es aceptada por un DFA / NDFA (Q, ∑, δ, q 0 , F), si
δ*(q0, S) ∈ F
El idioma L aceptado por DFA / NDFA es
{S | S ∈ ∑* and δ*(q0, S) ∈ F}
Una cadena S ′ no es aceptada por un DFA / NDFA (Q, ∑, δ, q 0 , F), iff
δ*(q0, S′) ∉ F
El idioma L ′ no aceptado por DFA / NDFA (Complemento del idioma aceptado L) es
{S | S ∈ ∑* and δ*(q0, S) ∉ F}
Example
Consideremos el DFA que se muestra en la Figura 1.3. Del DFA, se pueden derivar las cadenas aceptables.
Cadenas aceptadas por el DFA anterior: {0, 00, 11, 010, 101, ...........}
Cadenas no aceptadas por el DFA anterior: {1, 011, 111, ........}