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}*}
Publicación traducida automáticamente
Artículo escrito por Kanchan_Ray y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA