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