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

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 el segundo símbolo del lado izquierdo siempre es ‘b’.
Explicación: El idioma deseado será como:

L1 = {ab, aba, abaa, bb, bb, bbbb, ...........}

Aquí, como podemos ver, cada string del idioma que contiene ‘b’ como el segundo símbolo del lado izquierdo, pero el idioma a continuación no es aceptado por este DFA porque parte de la string del idioma a continuación no contiene ‘b’ como el segundo símbolo del lado izquierdo.

L2 = {ba, ba, babaaa..............}

Este lenguaje L2 no es aceptado por este DFA requerido porque no contiene ‘b’ como el segundo símbolo del lado izquierdo.
El diagrama de transición de estado del idioma deseado será el siguiente:

En el DFA anterior, el estado ‘W’ es el estado inicial que al obtener ‘a’ o ‘b’ como entrada, transita a un estado ‘X’. El estado ‘X’ al obtener ‘b’ como entrada, transita al estado final ‘Y’ y al obtener ‘a’ como entrada, transita a un estado muerto ‘Z’.

El estado final ‘Y’ al obtener ‘a’ o ‘b’ como entrada, permanece en el estado de sí mismo. El estado muerto ‘Z’ se llama muerto porque no puede ir al estado final al obtener cualquiera de los alfabetos de entrada.

Nota: El número de estados en el DFA anterior es (n+2), donde ‘n’ es el número del lado izquierdo de la string utilizada en el idioma anterior.

Problema-2: Construcción de un DFA mínimo que acepta un conjunto de strings sobre {a, b} en el que el tercer símbolo del lado izquierdo es siempre ‘b’.
Explicación: El idioma deseado será como:

L1 = {aab, baba, aabaa, bbb, abb, bbbb, ...........}

Aquí, como podemos ver, cada string del idioma que contiene ‘b’ como el tercer símbolo del lado izquierdo, pero el idioma a continuación no es aceptado por este DFA porque parte de la string del idioma a continuación no contiene ‘b’ como el tercer símbolo del lado izquierdo.

L2 = {baa, aba, baabaaa..............}

Este lenguaje L2 no es aceptado por este DFA requerido porque no contiene ‘b’ como el tercer símbolo del lado izquierdo.
El diagrama de transición de estado del idioma deseado será el siguiente:

En el DFA anterior, el estado ‘V’ es el estado inicial que al obtener ‘a’ o ‘b’ como entrada, transita al estado ‘W’. El estado ‘W’ es un estado que al obtener ‘a’ o ‘b’ como entrada, transita a un estado ‘X’. El estado ‘X’ al obtener ‘b’ como entrada, transita al estado final ‘Y’ y al obtener ‘a’ como entrada, transita a un estado muerto ‘Z’.

El estado final ‘Y’ al obtener ‘a’ o ‘b’ como entrada, permanece en el estado de sí mismo. El estado muerto ‘Z’ se llama muerto porque no puede ir al estado final al obtener cualquiera de los alfabetos de entrada.

Nota: El número de estados en el DFA anterior es (n+2), donde ‘n’ es el número del lado izquierdo de la string utilizada en el idioma anterior.