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

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *