Minimização DFA

Minimização DFA usando o teorema Myphill-Nerode

Algoritmo

Input - DFA

Output - DFA minimizado

Step 1- Desenhe uma tabela para todos os pares de estados (Q _i , Q _j ) não necessariamente conectados diretamente [Todos são desmarcados inicialmente]

Step 2- Considere todos os pares de estados (Q _i , Q _j ) no DFA onde Q _i ∈ F e Q _j ∉ F ou vice-versa e marque-os. [Aqui F é o conjunto de estados finais]

Step 3 - Repita esta etapa até que não possamos marcar mais estados -

Se houver um par não marcado (Q _i , Q _j ), marque-o se o par {δ (Q _i , A), δ (Q _i , A)} estiver marcado para algum alfabeto de entrada.

Step 4- Combine todos os pares não marcados (Q _i , Q _j ) e torne-os um único estado no DFA reduzido.

Exemplo

Vamos usar o Algoritmo 2 para minimizar o DFA mostrado abaixo.

Step 1 - Desenhamos uma tabela para todos os pares de estados.

	uma	b	c	d	e	f
uma
b
c
d
e
f

Step 2 - Marcamos os pares de estados.

	uma	b	c	d	e	f
uma
b
c	✔	✔
d	✔	✔
e	✔	✔
f			✔	✔	✔

Step 3- Tentaremos marcar os pares de estados, com a marca de verificação verde, transitivamente. Se inserirmos 1 no estado 'a' e 'f', ele irá para o estado 'c' e 'f' respectivamente. (c, f) já está marcado, portanto, marcaremos o par (a, f). Agora, inserimos 1 no estado 'b' e 'f'; ele irá para o estado 'd' e 'f' respectivamente. (d, f) já está marcado, portanto, marcaremos o par (b, f).

	uma	b	c	d	e	f
uma
b
c	✔	✔
d	✔	✔
e	✔	✔
f	✔	✔	✔	✔	✔

Após a etapa 3, temos as combinações de estado {a, b} {c, d} {c, e} {d, e} que não estão marcadas.

Podemos recombinar {c, d} {c, e} {d, e} em {c, d, e}

Portanto, temos dois estados combinados como - {a, b} e {c, d, e}

Portanto, o DFA minimizado final conterá três estados {f}, {a, b} e {c, d, e}

Minimização DFA usando o Teorema de Equivalência

Se X e Y são dois estados em um DFA, podemos combinar esses dois estados em {X, Y} se eles não forem distinguíveis. Dois estados são distinguíveis, se houver pelo menos uma string S, tal que um de δ (X, S) e δ (Y, S) está aceitando e outro não está aceitando. Portanto, um DFA é mínimo se e somente se todos os estados forem distinguíveis.

Algoritmo 3

Step 1 - Todos os estados Q são divididos em duas partições - final states e non-final states e são denotados por P₀. Todos os estados em uma partição são 0 ^th equivalente. Pegue um contadork e inicialize-o com 0.

Step 2- Incremente k em 1. Para cada partição em P _k , divida os estados em P _k em duas partições se eles forem k-distinguíveis. Dois estados dentro desta partição X e Y são k-distinguíveis se houver uma entradaS de tal modo que δ(X, S) e δ(Y, S) são (k-1) -distinguíveis.

Step 3- Se P _k ≠ P _k-1 , repita a Etapa 2, caso contrário, vá para a Etapa 4.

Step 4- Combine os k- ^ésimos conjuntos equivalentes e torne-os os novos estados do DFA reduzido.

Exemplo

Vamos considerar o seguinte DFA -

q	δ (q, 0)	δ (q, 1)
uma	b	c
b	uma	d
c	e	f
d	e	f
e	e	f
f	f	f

Vamos aplicar o algoritmo acima ao DFA acima -

• P ₀ = {(c, d, e), (a, b, f)}
• P ₁ = {(c, d, e), (a, b), (f)}
• P ₂ = {(c, d, e), (a, b), (f)}

Portanto, P ₁ = P ₂ .

Existem três estados no DFA reduzido. O DFA reduzido é o seguinte -

Q	δ (q, 0)	δ (q, 1)
(a, b)	(a, b)	(c, d, e)
(c, d, e)	(c, d, e)	(f)
(f)	(f)	(f)