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 *.