Diseño de autómatas finitos deterministas (Conjunto 3) – Part 1

Prerrequisito: Diseño de autómatas finitos , Diseño de autómatas finitos deterministas (Conjunto 2) 
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 aceptación de DFA sobre {a, b} donde cada string contiene ‘a’ como substring. 

Explicación: 
El idioma deseado será como: 
 

L1 = {a, aa, ab, ba, ..............}

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

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

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

En el DFA anterior, los estados ‘X’ e ‘Y’ son el estado inicial y final respectivamente, acepta todas las strings que contienen ‘a’ como substring. Aquí, como vemos, al obtener la entrada como ‘b’, permanece en el estado de ‘X’, pero al obtener ‘a’ como entrada, pasa al estado final ‘Y’ y, por lo tanto, dicha string es aceptada por DFA anterior. 

Problema 2: construcción de un conjunto mínimo de strings de aceptación de DFA sobre {a, b} donde cada string contiene ‘ab’ como substring. 

Explicación: El idioma deseado será como: 
 

L1 = {ab, aab, abb, bab, ..............}

Aquí, como podemos ver, cada string del idioma que contiene ‘ab’ como substring, pero el idioma a continuación no es aceptado por este DFA porque parte de la string del idioma a continuación no contiene ‘ab’ como substring. 
 

L2 = {aba, bba, bbbaaa, ..............}

El diagrama de transición de estado del idioma que contiene ‘ab’ como substring será como: 
 

En el DFA anterior, los estados ‘X’ y ‘Z’ son el estado inicial y final respectivamente, acepta todas las strings que contienen ‘ab’ como substring. Aquí, como vemos que al obtener ‘b’ como entrada, permanece en el estado inicial en sí mismo, al obtener ‘a’ como entrada, transita al estado ‘Y’ y luego al obtener ‘b’ finalmente transita al estado estado final ‘Z’ y, por lo tanto, este DFA acepta todo el idioma que contiene ‘ab’ como substring.