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

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 DFA mínimo que acepta un conjunto de strings sobre {a, b} en el que a ⁿ b ^m c ^l , donde n, m y l son mayores o iguales a 0.
Explicación: el idioma deseado será como :

L1 = {ε, a, aa, aaa, b, bb, bbb, c, cc, ccc, abc, ab, ac, ...........}

Nota: En la string anterior debe haber un orden como abc, es decir, no debe haber ninguna ‘a’ después de ‘b’ ni ninguna ‘a’ después de ‘c’, etc.

Aquí, como podemos ver, cada string del idioma que contiene a, b y c 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, b y c cuyo poder es mayor o igual a 0 o podrían no seguir el formato de a, b y c, es decir, no debería haber ninguna ‘a’ después de ‘b’ ni ninguna ‘a’ después de ‘c’, etc.

L2 = {ba, bac, bbacaa..............}

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

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

Otro estado final ‘Y’ al obtener ‘c’ como entrada, permanece en el estado de sí mismo y al obtener la entrada como ‘a’ o ‘b’ transita al mismo estado muerto ‘Z’. El estado ‘Z’ se denomina estado muerto porque no puede pasar a ninguno de los estados finales al obtener cualquiera de los alfabetos de 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 c ^l , donde n, m y l son mayores o iguales a 1.
Explicación: el idioma deseado será como :

L1 = {abc, aabc, aabbc, aabbcc, abbc, ...........}

Nota: En la string anterior debe haber un orden como abc, es decir, no debe haber ninguna ‘a’ después de ‘b’ ni ninguna ‘c’ después de ‘a’, etc.

Aquí, como podemos ver, cada string del idioma que contiene a, b y c 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, b y c cuyo poder es mayor o igual a 1 o podrían no seguir el formato de a, b y c, es decir, no debería haber ninguna ‘a’ después de ‘b’ ni ninguna ‘c’ después de ‘a’, etc.

L2 = {ba, bac, bbacaa..............}

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

En el DFA anterior, el el estado inicial ‘V’ al obtener ‘a’ como entrada, transita a un estado ‘W’ y al obtener ‘b’ o ‘c’ como entrada, transita a un estado muerto ‘Z’. El estado ‘W’ al obtener ‘b’ como entrada, permanece en el estado mismo o transita a un estado ‘X’ y al obtener ‘a’ o ‘c’ transita al mismo estado muerto ‘Z’. El estado ‘X’ al obtener ‘b’ como entrada permanece en el estado de sí mismo y al obtener ‘c’ como entrada transita al estado final ‘Y’ y al obtener ‘a’ como entrada transita a el mismo estado muerto ‘Z’.

El estado final ‘Y’ al obtener ‘c’ como entrada permanece en el estado de sí mismo y al obtener ‘a’ o ‘b’ como entrada transita al mismo estado muerto ‘Z’. El estado ‘Z’ se denomina estado muerto porque no puede pasar nunca al estado final al obtener cualquiera de los alfabetos de entrada.