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

Requisito previo: diseño de autómatas finitos
En este artículo, veremos algunos diseños de autómatas finitos deterministas (DFA).

Problema 1: construcción de un conjunto mínimo de strings de caracteres que acepta DFA sobre {a, b} en el que a ⁿ b ^m , donde n y m son mayores o iguales a 1.
Explicación: el lenguaje deseado será como:

L1 = {ab, aab, abb, aabb, aaabbb, aaabbbb, ...........}

Nota: En la string anterior no debe haber ninguna ‘a’ después de ‘b’.

Aquí, como podemos ver, cada string del idioma que contiene a y b cuyo poder es mayor o igual a 1, pero el idioma a continuación no es aceptado por este DFA porque parte de la string del idioma a continuación no contiene a y b cuyo poder es mayor o igual a 1.

L2 = {ε, a, b, ..............}

Este lenguaje L2 no es aceptado por este DFA requerido.
El diagrama de transición de estado del idioma deseado será el siguiente:

En el DFA anterior, el estado ‘W’ es el estado inicial y al obtener ‘a’ como entrada, transita al estado normal ‘X’ que al obtener ‘ a’ como entrada permanece en el estado de sí mismo y al obtener ‘b’ como entrada transita al estado final ‘Y’ que al obtener ‘b’ como entrada permanece en el estado de sí mismo y al obtener como la entrada transita al estado muerto ‘Z’ y cuando el estado inicial ‘W’ obtiene ‘b’ como entrada, entonces transita al estado muerto ‘Z’.

El estado ‘Z’ se llama estado muerto porque no puede pasar al estado final al recibir cualquier entrada.

Problema-2: Construcción de un DFA mínimo que acepta un conjunto de strings sobre {a, b} en el que a ⁿ b ^m , donde n y m son mayores o iguales a 0.
Explicación: El lenguaje deseado será como:

L1 = {ε, a, b, ab, aab, abb, aabb, aaabbb, aaabbbb, ...........}

Nota: En la string anterior no debe haber ninguna ‘a’ después de ‘b’.

Aquí, como podemos ver, cada string del idioma que contiene a y b cuyo poder es mayor o igual a 0, pero el idioma a continuación no es aceptado por este DFA porque parte de la string del idioma a continuación no contiene a y b cuyo poder es mayor o igual a 0 o podrían no seguir el formato de a y b, es decir, no debería haber ninguna ‘a’ después de ‘b’.

L2 = {ba, baa, bbaaa..............}

Este lenguaje L2 no es aceptado por este DFA requerido porque su string contiene ‘a’ después de ‘b’.
El diagrama de transición de estado del idioma deseado será el siguiente:

En el DFA anterior, el estado ‘X’ es el estado inicial y final que al obtener ‘a’ como entrada permanece en el estado de sí mismo y al obtener ‘b ‘ como entrada, transita a la ‘Y’ final que, al obtener ‘b’ como entrada, permanece en el estado de sí mismo y al obtener ‘a’ como entrada, transita al estado muerto ‘Z’.

El estado ‘Z’ se denomina estado muerto porque no puede pasar al estado final al obtener cualquier alfabeto de entrada.