Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 8)

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

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: Lenguaje regular,

L1 = {an | n≥ 1}  

El lenguaje del RE dado es-

{a, aa, aaa, ..........}

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’ al obtener ‘a’ como entrada, transita a un estado final ‘Z’ y así sucesivamente para los estados restantes. Por lo tanto, este FA acepta todas las strings del lenguaje RE dado.

Expresión regular 2: Lenguaje regular,

L2 = {anbm | n, m≥ 1}

.
El lenguaje del RE dado es-

{ab, aab, abb, aaaabb, ..........}

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

en el diagrama de transición anterior, como podemos ver que el estado inicial ‘X’ al obtener ‘a’ como entrada, transita a un
estado ‘Y’ y así sucesivamente para los estados restantes. Por lo tanto, este FA acepta todas las strings del lenguaje RE dado.

Expresión regular 3: Lenguaje regular,

L3 = (a+b)*  

El lenguaje del RE dado es-

{ε, a, aa, aaa, aabbb, ........} 

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 ‘Z’ al obtener ‘a’ o ‘b’ como entrada, permanece en el estado de sí mismo. Por lo tanto, este FA acepta todas las strings del lenguaje RE dado.

Nota: Los siguientes RE son equivalentes entre sí.

= (a+b)* 
= (a*+b*)* 
= (a*b*)* 
= (a*+b)* 
= (a+b*)* 
= a*(ba*)* 
= b*(ab*)* 

Expresión regular 4: Lenguaje regular,

L4 = {wwR | |w|=2, Σ={a, b}*} 

El lenguaje del RE dado es-

{aaaa, abba, baab, bbbb}

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

en el diagrama de transición anterior, como podemos ver que el estado inicial ‘A’ al obtener ‘a’ como entrada, transita a un estado ‘b’ y al obtener ‘b’ como entrada transita a un estado ‘H’ y así sucesivamente para los estados restantes. Por lo tanto, este FA acepta todas las strings del lenguaje RE dado.

Nota: La siguiente expresión no es una expresión regular porque la longitud de la string ‘w’ no está limitada.

{wwR | Σ={a, b}*}