T
AF
6
Formas normais para as linguagens
regulares
6.1
Autómatos Mínimos
Dada uma linguagem regular L, muitos são os autómatos determinísticos que a representam. Seja AL o conjunto dos autómatos tais que
(∀A)(A ∈ AL ⇒ L(A) = L).
DR
Os autómatos de AL não têm todos o mesmo número de estados e portanto a pergunta
que naturalmente surge é a da existência de um autómato mínimo (no sentido de ter o
número mínimo de estados) e do processo da sua obtenção. O teorema de Myhill-Nerode
(pág. 76) sujere que tal autómato existe assim como apresenta uma caracterização desse
autómato que conduz à sua construção.
Dado um autómato, comecemos por eliminar os estados que não são acessíveis a partir
do estado inicial, assim como aqueles dos quais não se pode chegar a um estado final.
Trivialmente, esta operação não altera a linguagem reconhecida pelo autómato inicial
(e só pode fazer diminuir o seu número de estados!). Nesta secção, a menos que seja
explícitamente dito o contrário, consideraremos sempre autómatos a que foram removidos
todos os estados pelo processo anterior.
A ideia por de trás da minimização de um DFA é a de eliminar estados que representem
(à luz do teorema de Myhill-Nerode) a mesma família de palavras. Seja A = #S, Σ, δ, s0, F$.
Em vez de tentarmos contruir directamente um autómato com o menor número de estados,
79
T
comecemos por estabelecer quais os pares de estados que são intrinsecamente diferentes, que representam diferentes linguagens e portanto não passiveis de serem colapsados
num mesmo estado no novo autómato que queremos construir. Chamemos a estes pares
distinguíveis. Sabemos que os estados finais e os estados não finais são, com certeza,
distinguíveis, pois os primeiros representam linguagens que contêm ε o que não é o caso
dos segundos.
Comecemos, então, por definir a seguinte relação, N ⊆ S2 , dos estados de S que
sabemos, à partida, serem distinguíveis:
N = {(s, s ! ) ∈ S2 | s ∈ F ∨ s ! ∈ F}.
(6.1)
AF
Para além destes pares de estados, dois estados, s e s ! , são distinguíveis se para um
dado símbolo, σ, as respectivas imagens por δ, δ(s, σ) e δ(s ! , σ), forem distinguíveis. Isto
corresponde a adicionar a N os pares que satisfazem a seguinte propriedade:
P(X) : (∀s, s ! ∈ S ∃σ ∈ Σ ((δ(s, σ), δ(s !, σ)) ∈ X) ⇒ ((s, s ! ) ∈ X)).
(6.2)
δ(s ! , ρ) ∈ F).
((s, s ! ) ∈ FP (N)) ⇔ (∃ρ)(!
δ(s, ρ) ∈ F ∨ !
(6.3)
Consideremos, agora, o fecho de P para N, FP (N). Esta nova relação FP (N), relaciona
pares de estados,(s, s ! ), para os quais existe uma palavra, ρ, tal que (!
δ(s, ρ), !
δ(s ! , ρ) ∈
FP (N)), ou seja
Problema 53 Provar a proposição contida na fórmula (6.3).
Seja R a relação complementar de FP (N). A relação R é uma relação de equivalência,
basta ver que
DR
(s, s ! ) ∈ R ⇔ (s, s ! ) '∈ FP (N) ⇔ (∀ρ ∈ Σ! )(!
δ(s, ρ), !
δ(s ! , ρ)) '∈ FP (N)
⇔ (∀ρ ∈ Σ! )(!
δ(s, ρ) ∈ F ⇔ !
δ(s ! , ρ) ∈ F).
Lema 6.1 Dado um autómato A = #S, Σ, δ, so, F$ consideremos um novo autómato
Am = #S/R, Σ, δm, [s0], Fm $ em que R é a relação de equivalência de indistiguibilidade
sobre S obtida como acabamos de descrever,
δm : S/R × Σ −→ s/R
e
([s], σ) )−→ [δ(s, σ)]
(6.4)
F = {[s] ∈ S/R | s ∈ F},
onde [s] representa, como costume, a classe de equivalência de R a que s pertence.
Então L(A) = L(Am ).
80
Dem. Seja ρ uma palavra aceite por A, então !
δ(s0 , ρ) ∈ F (por 4.3), mas como, para
qualquer relação de equivalência, se tem
então
T
(∀s)(s ∈ [s]),
"
#
!
δm ([s0 ], ρ) = !
δ(s0 , ρ) ∈ Fm .
Logo L(A) ⊆ L(Am ). Suponhamos agora que ρ = σ1 σ2 · · · σl ∈ L(Am ) (com
σ1 , σ2, . . . , σl ∈ Σ), ou seja
AF
!
δm ([s0 ], σ1σ2 · · · σl ) ∈ Fm .
Sejam s0 , s1 , . . . , sl tais que δm ([si−1 ], σi ) = [si ], para i ∈ [1, l], e tomemos s0! , s1! , . . . , sl!
!
com s0 = s0! , tais que δ(si−1
, σi ) = si! , para i ∈ [1, l]. Da definição de δm (6.4)
resulta que, para todo o i ∈ [0, l], si! ∈ [si ] (por indução sobre l). Pela definição
de R, cada uma das suas classes de equivalência, [s], ou estão integralmente
contidas em F, ou são disjuntas de F. Pelo que
!
δ(s0 , ρ) = sl! ∈ F,
ou seja ρ ∈ L(A). Logo L(A) = L(Am ).
!
Teorema 6.2 (autómato mínimo) Seja A um DFA, existe um DFA, Am , tal que
(L(Am ) = L(A)) ∧ (∀B (L(B) = L(A) ⇒ |Am | ≤ |B|)).
(6.5)
Este autómato mínimo, Am , é o único que satisfaz (6.5).
DR
Dem. Seja Am o autómato definido no Lema 6.1 e provemos que Am é mínimo, no
sentido que qualquer outro DFA B com menos estados que Am não é equivalente
a A. Seja então B = #S !, Σ, δ !, s0! , F ! $ um DFA com |B| < |Am | = n. Pela forma
como Am foi construído, sabemos que para qualquer par de estados existe uma
palavra que é “testemunha” que esses estados não são equivalentes, ou seja
δ([sj ], ρi,j ) ∈ Fm ))).
(∀i, j)(i, j ∈ [0, n − 1] ∧ i '= j ⇒ (∃ρi,j ∈ Σ! (!
δ([si ], ρi,j) ∈ Fm ∨ !
Como nestes autómatos todos os estados são acessíveis apartir do estado inicial
!
(ver a observacão da página 79), podemos tomar, por outro lado, ρ0! , ρ1! , . . . , ρn−1
tais que !
δ([s0 ], ρi!) = [si ], para i ∈ [0, n − 1]. Como |S ! | < n temos, pelo Princípio
de Dirichlet (ver 1.1) que
(∃k, k ! )(k, k ! ∈ [0, n − 1] ∧ k '= k ! ∧ δ!! (s0! , ρk! ) = δ!! (s0! , ρk! ! ).
81
Mas então
(ρk! ρk,k ! ∈ L(Am )) ∨ (ρk! ! ρk,k ! ∈ L(Am )))
enquanto
T
(ρk! ρk,k ! ∈ L(B)) ⇔ (ρk! ! ρk,k ! ∈ L(B)).
Pelo que L(Am ) '= L(B). Logo Am é mínimo.
AF
Provemos agora que Am é único (a menos de renomeação de estados). Suponhamos que para um outro DFA A ! = #S ! , Σ, δ !, s0! , F$ se tem |Am | = |A ! | = n.
Para cada par de estados deste autómato, si! , sj! , tem que existir uma palavra
que seja “testemunha” da sua não equivalência, porque senão seria possível,
aplicando o método aplicado a A, obter um autómato equivalente com menos
estados, que pelo que acabamos de provar, teria que ser não equivalente a Am .
Sejam então ρi,j ∈ Σ! , com i, j ∈ [0, n − 1], as referidas “testemunhas” de não
equivalência para os estados de A ! , ou seja
(∀i, j)((i, j ∈ [0, n − 1] ∧ i '= j) ⇒ (δ!! (si! , ρi,j ) ∈ F ! ∨ δ!! (sj! , ρi,j ) ∈ F !)).
Agora, ou temos
(∀ρ, ρ !)(ρ, ρ ! ∈ Σ! ⇒ (!
δm ([s0 ], ρ) = !
δm ([s0 ], ρ !)) ⇔ (δ!! (s0! , ρ) = δ!! (s0! , ρ !))),
e então é possível renomear os estados de A ! por forma a se ter
(∀ρ)(∀i)(ρ ∈ Σ! ∧ i ∈ [0, n − 1] ⇒ (!
δm ([s0 ], ρ) = [si ] ⇔ δ!! (s0! , ρ) = si! ))
(∀i)(i ∈ [0, n − 1] ⇒ (([si ] ∈ Fm ) ⇔ (si! ∈ F ! )))
e os dois autómatos são iguais. Ou
DR
(∃ρ, ρ !)(ρ, ρ ! ∈ Σ! ∧ ((!
δm ([s0 ], ρ) = !
δm ([s0 ], ρ !)) ∨ (δ!! (s0! , ρ) = δ!! (s0! , ρ !)))
e então, podemos concatenando a estas palavras, ρ e ρ ! , as “testemunhas”
apropriadas, provar que L(Am ) '= L(A !).
!
6.1.1
O algoritmo de Moore
O algoritmo de Moore, normalmente atribuído a Huffman [Huf54] e Moore [Moo56],
corresponde exactamente à construção da relação FP (N) referida no Lema 6.1. Vejamos
um exemplo.
Exemplo 6.3 Consideremos, então o DFA representado pelo diagrama seguinte.
82
a
a
s4
s7
a
s6
b
b
b
b
s5
s3
a
T
a
b
s0
b
s1
b
s2
b
a
AF
a
a
e encontremos o autómato determinístico mínimo equivalente utilizando o procedimento indicado na demonstração anterior.
Comecemos por marcar como distinguíveis todos os pares com um estado final e
outro não final. A tabela seguinte enumera os elementos de N.
×
×
×
×
×
×
×
×
×
s0
s1
×
×
×
×
s3
DR
s1
s2
s3
s4
s5
s6
s7
s2
×
s4
s5
×
s6
Comecemos a tentar encontrar mais elementos para acrescentar à relação, para obter
o seu fecho. Seja N1 a relação
$
%
!
!
N ∪ (s, s ) | ∃σ ∈ Σ δ(s, σ) ∈ N ∨ δ(s , σ) ∈ N .
83
Então,
(δ(s0 , b), δ(s1, b)) = (s4 , s2 ) ∈ N ⇒ (s0 , s1 ) ∈ N1
T
(δ(s0 , a), δ(s2, a)) = (s1 , s2 ) '∈ N ∧ (δ(s0 , b), δ(s2, b)) = (s4 , s3 ) '∈ N
(δ(s0 , a), δ(s5, a)) = (s1 , s2 ) '∈ N ∧ (δ(s0 , b), δ(s5, b)) = (s4 , s6 ) '∈ N
(δ(s0 , b), δ(s7, b)) = (s4 , s5 ) ∈ N ⇒ (s0 , s7 ) ∈ N1
(δ(s1 , b), δ(s2, b)) = (s2 , s3 ) ∈ N ⇒ (s1 , s2 ) ∈ N1
(δ(s1 , b), δ(s5, b)) = (s2 , s6 ) ∈ N ⇒ (s1 , s5 ) ∈ N1
(δ(s1 , a), δ(s7, a)) = (s1 , s7 ) '∈ N ∧ (δ(s1 , b), δ(s7, b)) = (s2 , s5 ) '∈ N
AF
(δ(s2 , a), δ(s5, a)) = (s2 , s2 ) '∈ N ∧ (δ(s2 , b), δ(s5, b)) = (s2 , s6 ) '∈ N
(δ(s2 , b), δ(s7, b)) = (s3 , s5 ) ∈ N ⇒ (s2 , s7 ) ∈ N1
(δ(s3 , b), δ(s4, b)) = (s6 , s5 ) ∈ N ⇒ (s3 , s4 ) ∈ N
(δ(s3 , a), δ(s6, a)) = (s1 , s7 ) '∈ N ∧ (δ(s3 , b), δ(s6, b)) = (s6 , s3 ) '∈ N
(δ(s4 , b), δ(s6, b)) = (s5 , s3 ) ∈ N ⇒ (s4 , s6 ) ∈ N1
(δ(s5 , b), δ(s7, b)) = (s6 , s5 ) ∈ N ⇒ (s5 , s7 ) ∈ N1 .
A tabela de N1 é então a seguinte.
×
s1
s2
s3
s4
s5
s6
s7
×
×
×
×
×
×
×
×
s2
×
s3
DR
×
×
s0
×
×
×
×
×
s1
×
×
×
s4
×
×
s5
×
s6
Tentemos acrescentar mais elementos, agora fazendo
$
!
!
%
N2 = N1 ∪ (s, s ) | ∃σ ∈ Σ δ(s, σ) ∈ N1 ∨ δ(s , σ) ∈ N1 .
Então, e escrevendo somente as clonclusões positivas, temos.
(δ(s0 , b), δ(s2, b)) = (s4 , s3 ) ∈ N1 ⇒ (s0 , s2 ) ∈ N2
(δ(s0 , a), δ(s5, a)) = (s1 , s2 ) ∈ N1 ⇒ (s0 , s5 ) ∈ N2 .
Que resulta na seguinte tabela.
84
×
×
×
×
×
s1
×
×
×
×
T
×
×
×
×
×
×
×
s0
s1
s2
s3
s4
s5
s6
s7
×
×
s2
×
s3
×
×
×
s4
×
×
s5
×
s6
AF
Um ciclo seguinte para tentar acrescentar mais pares, agora a N3 , mostra-se
infrutífero, pelo que o fecho para aquela propriedade P(X) (da demonstração de 6.1),
já foi atingido. A relação complementar desta tem então as seguintes classes de
equivalência
{{s0 }, {s1 , s7 }, {s2 , s5 }, {s3 , s6 }, {s4}} .
O autómato mínimo obtido é então o seguinte.
a
{s4 }
b
a
b
{s0 }
{s2 , s5 }
a
b
{s3 , s6 }
b
{s1 , s7 }
b
a
a
6.1.2
O algoritmo de Brzozowski
DR
Talvez o mais surpreendente dos aloritmos de minimização de autómatos seja o que se
deve a Brzozowski [Brz62]. Não tanto pela sua performance, que no pior caso pode ser
exponencial, mas pela simplicidade de descrição e pela não trivialmente evidente razão do
seu funcionamento. A prova da correcção do algoritmo, que aqui será apresentada, segue,
em termos gerais, a apresentada no artigo de Champarnaud et al [JMCP02].
Seja A um autómato finito, denotemos por R(A) o autómato reverso como o obtido
na Proposição 4.21. Sabemos, pela mesma proposição que
L(A)R = L(R(A)).
E portanto, aplicando mais uma vez o mesmo resultado, que
L(R(R(A)) = L(A).
Denotemos, agora, por D(A) o autómato determinístico obtido pelo método da construção de subconjuntos do Teorema 4.23. Então é fácil verificar, dado um autómato
85
finito A, que, por um lado, D(R(D(R(A)))) é um autómato determinístico, e por outro,
L(D(R(D(R(A))))) = L(A).
T
Lema 6.4 Seja A um NFA e A ! = D(A) o autómato determinístico equivalente obtido
pela construção dada pelo Teorema 4.23. Seja q ! um qualquer estado de A ! . A
linguagem direita de q ! é a união das linguagens direitas dos estados de A que
compõem q ! .
Teorema 6.5 (Brzozowski) Seja A um autómato finito, não necessariamente determinístico, o autómato
D(R(D(R(A))))
(6.6)
AF
é o autómato determinístico mínimo equivalente ao autómato A.
Exemplo 6.6 Consideremos o seguinte autómato A:
s0
1
s2 1
0
s1
1
s3
0
1
0
0
s4
1
s5
0, 1
0
O autómato R(A) é então
s0
1
s2
s1
0
1
s3
DR
0
0
0
s4
0
1
1
1
s5
0, 1
Para obtermos D(R(A)) procedemos como o indicado no Teorema 4.23.
→ {s2 , s3 , s4 }
!{s0 , s1 }
0
1
{s2 , s3 , s4 } {s0 , s1 }
{s0 , s1 }
∅
e o autómato obtido, chamando s0! = {s2 , s3 , s4 } e s1! = {s0 , s1 }, é
0
s0!
1
86
0
s1!
Agora, R(D(R(A))) vem
0
0
s0!
T
s1!
1
DR
AF
que já é determinístico, pelo que coincide com D(R(D(R(A)))), e portanto está encontrado
o DFA mínimo equivalente a A.
87