Prerrequisito: Autómatas finitos , Expresiones regulares, gramática y lenguaje , Diseño de autómatas finitos a partir de expresiones regulares (Conjunto 4)
En el siguiente artículo, veremos algunos diseños de autómatas finitos no deterministas a partir de la expresión regular dada:
Como NFA se puede cambiar a DFA correspondiente.
Expresión regular 1: Lenguaje regular,
L1 = ((a+b)(a+b)(a+b))*
El lenguaje del RE dado es,
{aaa, aba, baa, bba, aab, abb, bab, bbb,...}
La longitud de la cuerda es divisible por 3 ((longitud de la cuerda) mod 3 = 0).
Sus autómatas finitos serán como a continuación:
En el diagrama de transición anterior, como podemos ver que el estado inicial ‘W’ al obtener ‘a’ o ‘b’ como entrada, transita a un estado ‘X’ 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+b).((a+b)(a+b)(a+b))*
El lenguaje del RE dado es,
{aa, ab, ba, bb, aaaaa, aabab, ..........}
Longitud de string mod 3 = 2
Sus autómatas finitos serán como a continuación:
En el diagrama de transición anterior, como podemos ver que el estado inicial ‘W’ al obtener ‘a’ o ‘b’ como entrada, transita a un estado ‘X’ 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 = b*ab*ab*
El lenguaje del RE dado es,
{baa, babab, bbabbabb, ......}
Número de ‘a’ exactamente 2.
Sus autómatas finitos serán como a continuación:
En el diagrama de transición anterior, como podemos ver que el estado inicial ‘W’ al obtener ‘b’ como entrada, permanece en el estado de sí mismo y al obtener ‘a’ como entrada, transita a un estado ‘X’ 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 = b*ab*a(a+b)*
El lenguaje del RE dado es,
{baa, babab, bbabbaabb, ......}
Número de ‘a’ al menos 2.
Sus autómatas finitos serán como a continuación:
En el diagrama de transición anterior, como podemos ver que el estado inicial ‘W’ al obtener ‘b’ como entrada, permanece en el estado de sí mismo y al obtener ‘a’ como entrada, transita a un estado ‘X’ 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 = b*(ε+a)b*(ε+a)b*
El lenguaje del RE dado es,
{b, bb, bbb, bab, baab, babab, bbab, .....}
Número de ‘a’ como máximo 2.
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 ‘b’ como entrada, permanece en el estado de sí mismo y al obtener ‘a’ como entrada, transita a otro estado final ‘Y ‘ 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