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

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 cada ‘a’ va seguida de una ‘bb’.
Explicación: El idioma deseado será como:

L1 = {ε, abb, abbabb, bbbbabb, abbabbabbabbabbbb, ..............}

Aquí, como podemos ver, cada string del idioma que contiene ‘a’ solo está seguida de ‘bb’, pero este DFA no acepta el siguiente idioma porque parte de la string del siguiente idioma no contiene ‘a’ seguido de ‘cama y desayuno’.

L2 = {ba, baab, bbaba, ..............}

El diagrama de transición de estado del idioma que contiene ‘a’ seguido de ‘bb’ será como:

En el DFA anterior, el estado ‘v’ es el estado inicial y final también, que al obtener ‘b’ como entrada permanece en el estado de sí mismo y al obtener ‘a’ como entrada, transita a un estado normal ‘W’ que al obtener ‘a’ como entrada, transita al estado muerto ‘Z’ y al obtener ‘b’ como entrada transita a el estado normal ‘X’ que al obtener ‘b’ como entrada transita al estado final ‘V’ y al obtener ‘a’ como entrada transita al mismo estado muerto ‘Z’. El estado ‘Z’ se llama estado muerto porque al recibir cualquier entrada no puede transitar a ninguno de los estados finales nunca.

Problema 2: construcción de un conjunto mínimo de strings de caracteres que acepte DFA sobre {a, b} en el que cada ‘a’ nunca vaya seguida de ‘bb’.
Explicación: El idioma deseado será como:

L1 = {ε, a, aa, aabaa, b, bb, bbbbba, ..............}

Aquí, como podemos ver, cada string del idioma que contiene ‘a’ nunca va seguida de ‘bb’, pero este DFA no acepta el siguiente idioma porque parte de la string del siguiente idioma que contiene ‘a’ va seguida de ‘ cama y desayuno’.

L2 = {abb, babbabb, bbaba, ..............}

El diagrama de transición de estado del idioma que contiene ‘a’ nunca será seguido por ‘bb’ será como:

En el DFA anterior, el estado ‘W’ es el estado inicial y final también que al obtener ‘b’ como entrada permanece en el estado de sí mismo y al obtener ‘a’ como entrada, transita al estado final ‘X’, que al obtener ‘a’ como entrada, permanece en el estado de ‘X’ y obtiene ‘b’ como entrada transita al estado final ‘Y’ que al obtener ‘a’ como entrada transita a otro estado final ‘X’ y el estado final ‘Y’ al obtener ‘b’ como entrada transita al estado muerto ‘Z’ . El estado ‘Z’ se llama estado muerto porque al obtener cualquier entrada no puede pasar a ningún estado final.