Teorema de Arden
Para encontrar una expresión regular de un autómata finito, usamos el teorema de Arden junto con las propiedades de las expresiones regulares.
Statement -
Dejar P y Q ser dos expresiones regulares.
Si P no contiene una cadena nula, entonces R = Q + RP tiene una solución única que es R = QP*
Proof -
R = Q + (Q + RP) P [Después de poner el valor R = Q + RP]
= Q + QP + RPP
Cuando ponemos el valor de R recursivamente una y otra vez, obtenemos la siguiente ecuación:
R = Q + QP + QP 2 + QP 3 … ..
R = Q (ε + P + P 2 + P 3 +….)
R = QP * [Como P * representa (ε + P + P2 + P3 +….)]
Por lo tanto, probado.
Supuestos para aplicar el teorema de Arden
- El diagrama de transición no debe tener transiciones NULL
- Debe tener solo un estado inicial
Método
Step 1- Cree ecuaciones como la siguiente forma para todos los estados del DFA que tienen n estados con estado inicial q 1 .
q 1 = q 1 R 11 + q 2 R 21 +… + q n R n1 + ε
q 2 = q 1 R 12 + q 2 R 22 +… + q n R n2
…………………………
…………………………
…………………………
…………………………
q n = q 1 R 1n + q 2 R 2n +… + q n R nn
Rij representa el conjunto de etiquetas de bordes de qi a qj, si no existe tal ventaja, entonces Rij = ∅
Step 2 - Resuelva estas ecuaciones para obtener la ecuación del estado final en términos de Rij
Problem
Construya una expresión regular correspondiente a los autómatas que se indican a continuación:
Solution -
Aquí el estado inicial y el estado final es q1.
Las ecuaciones para los tres estados q1, q2 y q3 son las siguientes:
q 1 = q 1 a + q 3 a + ε (ε mover es porque q1 es el estado inicial0
q 2 = q 1 b + q 2 b + q 3 b
q 3 = q 2 una
Ahora, resolveremos estas tres ecuaciones:
q 2 = q 1 b + q 2 b + q 3 b
= q 1 b + q 2 b + (q 2 a) b (Sustituyendo el valor de q 3 )
= q 1 segundo + q 2 ( segundo + ab)
= q 1 b (b + ab) * (Aplicando el teorema de Arden)
q 1 = q 1 una + q 3 una + ε
= q 1 a + q 2 aa + ε (Sustituyendo el valor de q 3 )
= q 1 a + q 1 b (b + ab *) aa + ε (Sustituyendo el valor de q 2 )
= q 1 (a + b (b + ab) * aa) + ε
= ε (a + b (b + ab) * aa) *
= (a + b (b + ab) * aa) *
Por tanto, la expresión regular es (a + b (b + ab) * aa) *.
Problem
Construya una expresión regular correspondiente a los autómatas que se indican a continuación:
Solution -
Aquí el estado inicial es q 1 y el estado final es q 2
Ahora escribimos las ecuaciones:
q 1 = q 1 0 + ε
q 2 = q 1 1 + q 2 0
q 3 = q 2 1 + q 3 0 + q 3 1
Ahora, resolveremos estas tres ecuaciones:
q 1 = ε0 * [Como, εR = R]
Entonces, q 1 = 0 *
q 2 = 0 * 1 + q 2 0
Entonces, q 2 = 0 * 1 (0) * [Según el teorema de Arden]
Por tanto, la expresión regular es 0 * 10 *.