Conversión de un NFA en un DFA
Para cada NFA existe un DFA equivalente (entendiendo por equivalencia que reconoce el mismo lenguaje) y viceversa
- Todo DFA es un caso particular de NFA en el que se verifica que ?p?Q, ?a??, |?(q, a)|=1 y no hay ?-transiciones: ?q?Q, ?(q, ?)= ?
- Dado un NFA M?(?, Q, q0, F, ?) se puede construir un DFA equivalente M’? (?, Q’, q0’, F’, ?) con el siguiente algoritmo (construcción de subconjuntos):
- Q’ = ?(Q)
- q0’ = ?-clausura(q0)
- F’ = {c | c?Q’, ?q?c y q?F}
- ?(c, a)={c’ | c’ = ?q?c ?(q, a)}