Que-1: Dibuje un autómata finito determinista y no determinista que acepte 00 y 11 al final de una string que contenga 0, 1, por ejemplo, 01010100 pero no 000111010.
Explicación: diseñe un DFA y NFA de una misma string si el valor de entrada alcanza el estado final, entonces es aceptable; de lo contrario, no es aceptable.
NFA de la string dada es el siguiente:
El DFA de la string dada es el siguiente:
Aquí, q0 muestra el estado inicial, q1 y q2 son los estados de transición y q3 y q4 son los estados finales.
Nota: NFA y DFA tienen el mismo poder, lo que significa que si NFA puede reconocer un idioma L, entonces DFA también puede definirse para hacerlo y si DFA puede reconocer un idioma L, entonces NFA también puede definirse para hacerlo.
Que-2: Dibuje un autómata finito determinista y no determinista que acepte una string que contenga «el» en cualquier parte de una string de {az}, por ejemplo, «allí» pero no «aquellos».
Explicación: diseñe un DFA y NFA de una misma string si el valor de entrada alcanza el estado final, entonces es aceptable; de lo contrario, no es aceptable. Es aplicable para todos los DFA y NFA. Dado que es más fácil salir de NFA que de DFA, primero haga su NFA y luego pase por DFA.
NFA de la string dada es el siguiente:
El DFA de la string dada es el siguiente:
Aquí, q0 muestra el estado inicial, q1 y q2 son los estados de transición y q3 es el estado final.
Que-3: Dibuje un autómata finito determinista y no determinista que acepte una string que contenga «ing» al final de una string en una string de {az}, por ejemplo, «cualquier cosa» pero no «cualquier lugar».
Explicación: diseñe un DFA y NFA de una misma string si el valor de entrada alcanza el estado final, entonces es aceptable; de lo contrario, no es aceptable. Es aplicable para todos los DFA y NFA.
NFA de la string dada es el siguiente:
El DFA de la string dada es el siguiente:
Aquí, q0 muestra el estado inicial, q1 y q2 son los estados de transición y q3 es el estado final.