Autómatas finitos y expresiones regulares
Aunque pudiera parecer que los autómatas finitos no deterministas tienen mayor capacidad de cómputo que los deterministas, hay un resultado que indica que ambos tipos de autómatas reconocen el mismo tipo de lenguajes: los lenguajes regulares
- Acabamos de ver que todo NFA se puede transformar en un DFA equivalente
- El siguiente resultado nos servirá para enlazar expresiones regulares y autómatas finitos