Diseño de autómatas finitos no deterministas (Conjunto 5)

Prerrequisito: Introducción a los autómatas finitos
En este artículo, veremos algunos diseños de autómatas finitos no deterministas (NFA).

Problema-1: Construcción de un NFA mínimo que acepta un conjunto de strings sobre {a, b} en el que cada string del idioma contiene ‘ab’ como substring.
Explicación: El idioma deseado será como:

L1 = {ab, abba, abaa, ...........}

Aquí, como podemos ver, cada string del idioma anterior contiene ‘ab’ como substring, pero el idioma siguiente no es aceptado por este NFA porque parte de la string del idioma siguiente no contiene ‘ab’ como substring.

L2 = {bb, b, bbbb, .............}

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 en obteniendo ‘b’ como entrada, permanece en el estado de sí mismo.

El estado ‘Y’ al obtener ‘b’ como entrada transmite a un estado final ‘Z’. El estado final ‘Z’ al obtener ‘a’ o ‘b’ como entrada, permanece en el estado de sí mismo.

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 contiene ‘ab’ como substring.
Explicación: El idioma deseado será como:

L1 = {b, bb, bbbb, ...........}

Aquí, como podemos ver, cada string del lenguaje anterior no contiene ‘ab’ como substring. Pero el lenguaje a continuación no es aceptado por este NFA porque parte de la string del lenguaje a continuación contiene ‘ab’ como substring.

L2 = {ab, aba, ababaab..............}

El diagrama de transición de estado del idioma deseado será el siguiente:

En el NFA anterior, el estado inicial y final ‘X’ al obtener ‘b’ como entrada permanece en el estado de sí mismo y al obtener ‘a’ como entrada transita a otro estado final ‘Y’.

Otro estado final ‘Y’ al obtener ‘a’ como entrada, permanece en el estado de sí mismo.