Requisito previo: Introducción a los autómatas finitos
Problema-1:
Construcción de un NFA mínimo que acepta un conjunto de strings sobre {a, b} en el que cada string del lenguaje termina con ‘ab’.
Explicación:
El idioma deseado será como:
L1 = {ab, abbab, abaab, ...........}
Aquí, como podemos ver, cada string del idioma anterior termina con ‘ab’, pero el idioma siguiente no es aceptado por este NFA porque parte de la string del idioma siguiente no termina con ‘ab’.
L2 = {bba, abb, aaabbbb, .............}
El diagrama de transición de estado del idioma deseado será el siguiente:
En el NFA anterior, el estado inicial ‘X’ al obtener ‘a’ como entrada permanece en el estado de sí mismo o transita a un estado ‘Y’ y al obtener ‘b’ como entrada permanece en el estado de sí mismo. El estado ‘Y’ al obtener ‘b’ como entrada transmite a un estado final ‘Z’.
Problema-2:
Construcción de un NFA mínimo que acepta un conjunto de strings sobre {a, b} en el que cada string del idioma no termina con ‘ab’.
Explicación: El idioma deseado será como:
L1 = {bba, abb, aaabbbb, .............}
Aquí, como podemos ver, cada string del idioma anterior no termina con ‘ab’, pero el idioma siguiente no es aceptado por este NFA porque parte de la string del idioma siguiente termina con ‘ab’.
L2 = {ab, abab, ababaab..............}
El diagrama de transición de estado del idioma deseado será el siguiente:
En el NFA anterior, el estado inicial ‘X’ al obtener ‘a’ como entrada permanece en el estado de sí mismo y al obtener ‘b’ como entrada se transmite a un estado ‘Y’. El estado ‘Y’ al obtener ‘b’ como entrada, permanece en el estado de sí mismo o se transmite a un estado final ‘Z’. El estado final ‘Z’ al obtener ‘a’ como entrada, permanece en el estado de sí mismo.
Publicación traducida automáticamente
Artículo escrito por Kanchan_Ray y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA