Estados inúteis

Um autômato finito pode ter estados dos quais não é possível chegar a um estado final e que, por isso, são inúteis. Esses estados são chamados de estados inúteis. Normalmente queremos removê-los, porque eles apenas complicam o autômato inteiro sem necessidade.

Exemplo de estados inúteis

Considere este autômato finito:

Vemos que, no momento em que chegamos aos estados q₄ ou q₅, nunca mais conseguiremos chegar a um dos estados finais q₁ ou q₂. Esses estados são, assim, inúteis e podemos simplesmente removê-los, obtendo um novo autômato que seria, no entanto, equivalente; ele aceitaria a mesma linguagem. Depois de apagar os estados inúteis, o autômato ficaria assim:

Ele aceitaria, portanto, a mesma linguagem. No entanto, há momentos em que convém ter alguns estados inúteis — por exemplo, quando construímos um autômato completo.

Definição de estado inútil

Considere um autômato finito A = ⟨Q, Σ, δ, q₀, F⟩. Dizemos que um estado q ∈ Q é inútil se não existe nenhuma palavra w ∈ Σ^∗ nem nenhum estado q_f ∈ F tal que

$$⟨q,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩.$$

Como remover os estados inúteis

Supomos que na entrada temos um autômato A = ⟨Q, Σ, δ, q₀, F⟩ que já não tem estados inacessíveis. Vamos encontrando aos poucos os estados que levam a estados finais, depois os estados que levam a estados que levam a estados finais, e assim sucessivamente. Assim obtemos o conjunto de todos os estados que não são inúteis. No começo estabelecemos S₀ = F. Vamos construir os outros conjuntos S_i para i ∈ ℕ^* segundo esta regra:

$$S_i=\{q\in Q|\mathrm{\exists }a\in \mathrm{\Sigma }:\delta (q,a)\in S_{i-1}\}\cup S_{i-1}$$

Podemos expressar o conjunto resultante de todos os estados que não são inúteis assim:

$$\bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

E o conjunto dos estados inúteis como

$$Q\setminus \bigcup _{i=1}^{\mathrm{\infty }}{S}_i.$$

Em outras palavras: se vale S_i = S_{i + 1}, então o conjunto Q ∖ S_i contém os estados inúteis. Vamos ilustrar o procedimento com este autômato:

Primeiro estabelecemos a igualdade S₀ = {q₁, q₂}. Em seguida construímos o conjunto S₁ acrescentando ao conjunto S₀ todos os estados que levam a um dos estados do conjunto S₀. Acrescentamos, assim, os estados q₀ e q₃, porque de q₀ sai uma transição para q₁ e de q₃ sai uma transição para q₂. Obtemos S₁ = {q₀, q₁, q₂, q₃}. Como S₀ ≠ S₁, continuamos.

Construímos o conjunto S₂. Procuramos, então, todos os estados dos quais se pode chegar a S₁ e que ainda não estão em S₁. É um único estado, q₆, do qual se pode chegar ao estado q₃. Obtemos S₂ = {q₀, q₁, q₂, q₃, q₆}. Como S₁ ≠ S₂, continuamos.

Construímos o conjunto S₃. Existe algum estado novo do qual se possa chegar a algum dos estados de S₂? Não existe: dos estados q₄ e q₅ não se pode chegar a nenhum dos estados de S₂, e os outros estados já estão em S₂. Portanto, S₃ = {q₀, q₁, q₂, q₃, q₆}. Como S₂ = S₃, o algoritmo termina, e o conjunto S₂ representa o conjunto dos estados que não são inúteis. O conjunto {q₄, q₅} é o conjunto dos estados que são inúteis.

Formalmente, construímos o novo autômato equivalente sem estados inúteis assim. Temos o autômato A = ⟨Q, Σ, δ, q₀, F⟩ e construímos para ele o autômato equivalente A′ = ⟨Q′, Σ, δ′, q₀, F⟩ sem estados inúteis.

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a), se δ(q, a) ∈ Q′; caso contrário, δ′(q, a) não está definida

Fontes

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools