Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 3) – Part 1

Prerrequisito: Autómatas finitos , Expresiones regulares, gramática y lenguaje , Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 2)

En el siguiente artículo, veremos algunos diseños de autómatas finitos a partir de la expresión regular dada.

Expresión regular 1: ‘ab*’ (‘a’ seguido de cualquier número de ‘b’). El lenguaje del RE dado es,

L1 = {a, ab, abb, abbb, .........} 

Sus autómatas finitos serán como a continuación:

en el diagrama de transición anterior, como podemos ver que el estado ‘X’ al obtener ‘a’ como entrada, transita a un estado final ‘Y’ que al obtener ‘b’ como entrada permanece en el estado de sí mismo. Por lo tanto, este FA acepta todas las strings del lenguaje RE dado.

Expresión regular 2: ‘(ab)*’ (‘a’ seguida de ‘b’ pero la substring ‘ab’ puede repetirse cualquier cantidad de veces). El lenguaje del RE dado es,

L2 = {ε, ab, abab, ababab, .........} 

Sus autómatas finitos serán como a continuación:

en el diagrama de transición anterior, como podemos ver que el estado inicial y final ‘X’ al obtener ‘a’ como entrada, transita a un estado final ‘Y’ que al obtener ‘b’ como la entrada vuelve al estado ‘X’. Por lo tanto, este FA acepta todas las strings del lenguaje RE dado.

Expresión regular 3: ‘(a+b)*’ (‘a’ unión ‘b’ pero la substring ‘a+b’ se puede repetir cualquier número de veces). El lenguaje del RE dado es,

L3 = {ε, a, b, aa, aaab, bbbbb, ba, .......} 

El idioma que contiene ε y cualquier número de ‘a’ o ‘b’ o ambos combinados.
Sus autómatas finitos serán como a continuación:

en el diagrama de transición anterior, como podemos ver que el estado ‘X’ al obtener ‘a’ como entrada, permanece en el estado de sí mismo y al obtener ‘b’ como la entrada a la que transita y otro estado final ‘Y’ que al tomar como entrada ‘b’ o ‘a’ queda en el estado de sí mismo. Por lo tanto, este FA acepta todas las strings del lenguaje RE dado.

Nota: el DFA mínimo de la expresión regular (a+b)* tendrá un solo estado, que es tanto el estado inicial como el final. Esto contendrá solo el bucle del alfabeto ‘a’ y ‘b’.

Expresión regular 4: ‘(ab+ba)*’ (‘ab’ unión ‘ba’ pero la substring ‘ab+ba’ puede repetirse cualquier número de veces). El lenguaje del RE dado es,

L4 = {ε, ab, abab, abba, ba, baba, ........ } 

El idioma que contiene ε y cualquier número de ‘ab’ o ‘ba’ o ambos combinados.
Sus autómatas finitos serán como a continuación:

En el diagrama de transición anterior, el estado inicial y final ‘X’ al obtener ‘a’ como entrada pasa al estado ‘Y’ y al obtener ‘b’ como entrada pasa a otro estado ‘Z’ y así sucesivamente para los estados restantes. Por lo tanto, este FA acepta todas las strings del lenguaje RE dado.

Expresión regular 5: ‘a+’ (cualquier número de ‘a’ excepto ε).
El lenguaje del RE dado es

L5 = {a, aa, aaa, aaaa, .........} 

Sus autómatas finitos serán como a continuación:

en el diagrama de transición anterior, el estado inicial ‘X’ al obtener ‘a’ como entrada, transita a un estado final ‘Y’ que al obtener ‘a’ como entrada permanece en el estado de sí mismo. Por lo tanto, este FA acepta todas las strings del lenguaje RE dado.