Prerrequisito: Autómatas finitos , Expresiones regulares, gramática y lenguaje , Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 5)
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 = a(a+b)*
El lenguaje del RE dado es,
{aaa, aba, baa, bba}
Las strings siempre comienzan con ‘a’.
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 = (a+b)*a
El lenguaje del RE dado es,
{aaa, aba, baa, bba}
Las strings siempre terminan en ‘a’.
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 al obtener ‘b’ como entrada permanece en el estado de sí mismo y así sucesivamente para los demás estados. Por lo tanto, este FA acepta todas las strings del lenguaje RE dado.
Expresión regular 3: Lenguaje regular,
L3 = (a+b)*a(a+b)*
El lenguaje del RE dado es,
{aaa, aba, baa, bba}
Strings que contienen ‘a’ como el alfabeto.
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 ‘b’ como entrada, permanece en el estado de sí mismo 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 4: Lenguaje regular,
L4 = (a(a+b)*b)+(b(a+b)*a)
El lenguaje del RE dado es,
{aab, abb, baa, bba}
Las strings comienzan y terminan con diferentes símbolos.
Sus autómatas finitos serán como a continuación:
en el diagrama de transición anterior, como podemos ver que el estado inicial ‘V’ al obtener ‘a’ como entrada, transita a un estado ‘W’ y así sucesivamente para los estados restantes. Por lo tanto, este FA acepta todas las strings del lenguaje RE dado.
Expresión regular 5: Lenguaje regular,
L5 = (a(a+b)*a)+(b(a+b)*b)+a+b+ε
El lenguaje del RE dado es,
{&epsilon, a, b, aba, bab, bbab}
Las strings comienzan y terminan con los mismos símbolos.
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 ‘V’ al obtener ‘a’ como entrada, transita a otro estado final ‘W’ y así sucesivamente para los estados restantes . Por lo tanto, este FA acepta todas las strings del lenguaje RE dado.
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