Teorema de Arden

A fim de descobrir uma expressão regular de um autômato finito, usamos o Teorema de Arden junto com as propriedades das expressões regulares.

Statement -

Deixei P e Q ser duas expressões regulares.

E se P não contém string nula, então R = Q + RP tem uma solução única que é R = QP*

Proof -

R = Q + (Q + RP) P [Depois de colocar o valor R = Q + RP]

= Q + QP + RPP

Quando colocamos o valor de R recursivamente uma e outra vez, obtemos a seguinte equação -

R = Q + QP + QP 2 + QP 3 ... ..

R = Q (ε + P + P 2 + P 3 +….)

R = QP * [Como P * representa (ε + P + P2 + P3 +….)]

Conseqüentemente, provado.

Suposições para a aplicação do teorema de Arden

  • O diagrama de transição não deve ter transições NULL
  • Deve ter apenas um estado inicial

Método

Step 1- Crie equações da seguinte forma para todos os estados do DFA com n estados com 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 o conjunto de rótulos de bordas de qi para qj, se tal vantagem não existe, então Rij = ∅

Step 2 - Resolva essas equações para obter a equação para o estado final em termos de Rij

Problem

Construa uma expressão regular correspondente ao autômato dado abaixo -

Solution -

Aqui, o estado inicial e o estado final são q1.

As equações para os três estados q1, q2 e q3 são as seguintes -

q 1 = q 1 a + q 3 a + ε (ε movimento é porque q1 é o estado inicial0

q 2 = q 1 b + q 2 b + q 3 b

q 3 = q 2 a

Agora, vamos resolver essas três equações -

q 2 = q 1 b + q 2 b + q 3 b

= q 1 b + q 2 b + (q 2 a) b (valor de substituição de q 3 )

= q 1 b + q 2 (b + ab)

= q 1 b (b + ab) * (Aplicando o Teorema de Arden)

q 1 = q 1 a + q 3 a + ε

= q 1 a + q 2 aa + ε (substituindo o valor de q 3 )

= q 1 a + q 1 b (b + ab *) aa + ε (substituindo o valor de q 2 )

= q 1 (a + b (b + ab) * aa) + ε

= ε (a + b (b + ab) * aa) *

= (a + b (b + ab) * aa) *

Portanto, a expressão regular é (a + b (b + ab) * aa) *.

Problem

Construa uma expressão regular correspondente ao autômato dado abaixo -

Solution -

Aqui, o estado inicial é q 1 e o estado final é q 2

Agora vamos escrever as equações -

q 1 = q 1 0 + ε

q 2 = q 1 1 + q 2 0

q 3 = q 2 1 + q 3 0 + q 3 1

Agora, vamos resolver essas três equações -

q 1 = ε0 * [As, εR = R]

Então, q 1 = 0 *

q 2 = 0 * 1 + q 2 0

Então, q 2 = 0 * 1 (0) * [Pelo teorema de Arden]

Portanto, a expressão regular é 0 * 10 *.