Máquinas NFA que aceptan todas las strings que terminan o no terminan con la substring ‘ab’

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.