Teorema de Arden y aplicaciones desafiantes | conjunto 2

Haber adquirido el conocimiento de cómo dibujar una máquina de estados finitos básica (DFA, NFA o 
-NFA). Nos dirigimos a derivar una expresión regular de la máquina de estado proporcionada. 

Para ciertos ejemplos proporcionados a continuación, es bastante simple derivarlo. 
 

Pero para el siguiente ejemplo, es bastante difícil derivar la expresión regular simplemente observando la máquina de estados finitos. Para este propósito, hacemos uso del teorema de Arden para simplificar nuestras ecuaciones de estado individuales y llegar a nuestra ecuación de estado final (que puede o no ser la versión simplificada) 

El teorema de Arden establece que, si P & Q son dos expresiones regulares sobre  , y si P no contiene  , entonces la siguiente ecuación R dada por R = Q + RP tiene solución única ; R = QP* 
 

PROOF  :- 
R = Q + RP
R = Q + QP*P   ( Substituting the value of R )
R = Q( + P*P)

R = QP *( P*P = ,  +  = P* )

Resolvamos los autómatas provistos arriba con la ayuda del Teorema de Arden. 

Vemos que en el estado C, hay una transición de estado proveniente de B cuando a es la entrada 

 C = Ba  

En el estado B, hay un bucle automático en la entrada b, una transición desde A cuando la entrada es a, una transición desde el estado C cuando la entrada es b 

 B = Bb + Cb + Aa  

En el estado A, hay una  transición (siendo el estado de inicio,  se debe incluir la transición), un bucle automático en la entrada a, una transición desde B cuando la entrada es b. 

 A =   + Aa + Bb  

Poniendo (2) en (1), obtenemos 
 

C = Ba
C = (Aa + Bb + Cb)a
C = Aaa + Bba + Cba

Poniendo (1) en (2), obtenemos 

B = Bb + Cb + Aa
B = Aa + Bb + (Ba)b
B = Aa + B(b + ab)
B = Aa(b + ab)*  (Using R = QP*)

Poniendo (2) en (3), obtenemos 

A =  + Aa + Bb
A =  + Aa + Aa(b + ab)*b
A =  + A(a + a(b + ab)*b)
A =  (a + a(b + ab)*b)*
A = (a + a(b + ab)*b)*

Como paso final, combinemos todas las ecuaciones simplificadas en el estado final C 

C = Ba
C = Aa(b + ab)*a
C = (a + a(b + ab)*b)* a (b + ab)* a

Ahora bien, este ejemplo corresponde a la derivación directa de un NFA proporcionado a una expresión regular. 

Digamos, nos encontramos con un problema que va como 

Problema: Derivar una expresión regular para representar un idioma que tiene incluso no. de como 

Para este caso, es difícil llegar a una expresión regular con solo una metodología de prueba y error. 
Podríamos encontrar soluciones de muestra como: 

lo que podría satisfacer algunos casos, pero también conduce a casos no deseados y casos faltantes con a y b alternativos. 
La mejor manera de resolver este problema es dibujar primero una máquina de estados finitos para el mismo y luego derivar la expresión regular del mismo. 

La siguiente figura muestra el DFA para el problema proporcionado 
 

Ahora que tenemos el AFD, resolvámoslo usando el Teorema de ecuaciones de estado individuales de Arden. 

Vemos que en el estado A, hay un autobucle con la entrada b y una transición desde B con la entrada a 
 

A =  + Ab + Ba 

Vemos que en el estado B, hay un bucle automático en la entrada b y una transición desde A cuando la entrada es a. 

B = Aa + Bb

Tomando la ecuación para B, podemos aplicar el teorema de Arden 
 

B = Aa + Bb
B = Aab*

Sustituyendo el valor de B en A obtenemos 
 

A =  + Ab + Ba
A =  + Ab + (Aab*)a
A =  ( b + ab*a )*
A = ( b + ab*a )*

Por lo tanto, la expresión regular para el problema proporcionado es RE: (b + ab*a)* 

Vemos que el teorema de Arden se puede utilizar como una poderosa herramienta de simplificación para determinar las Expresiones Regulares y también para diseñar la Máquina de Estados Finitos deseada a partir de las mismas. 

Por favor refiérase al Juego 1