✖

Estados inacessíveis

Um autômato finito pode ter estados aos quais não é possível chegar. Esses estados são chamados de estados inacessíveis. Normalmente queremos removê-los, porque eles apenas complicam o autômato inteiro sem necessidade.

Exemplo de estados inacessíveis

Considere este autômato:

Vemos que, não importa o que façamos, nunca chegaremos ao estado q3, porque nenhuma transição leva a ele. Dizemos, então, que o estado q3 é inacessível. Uma pergunta: o estado q3 seria acessível se alguma transição de outro estado levasse a ele? Se levássemos uma aresta de um dos estados q0, q1, q2, q5, ele seria acessível. Se acrescentássemos mais um nó e levássemos uma transição dele…

…então, é claro, os dois estados, q3 e q4, seriam inacessíveis.

Definição de estado inacessível

Primeiro definimos o estado acessível. Considere um autômato finito A = ⟨Q, Σ, δ, q0, F⟩. Dizemos que um estado q ∈ Q é acessível se existe uma palavra w ∈ Σ∗ tal que

⟨q0,w⟩↦∗⟨q,ε⟩.

Um estado q ∈ Q é inacessível se não é acessível.

Como remover os estados inacessíveis

Se o autômato já tem alguns estados inacessíveis, convém removê-los. Construímos, assim, um autômato equivalente A′ = ⟨Q′, Σ, δ′, q0, F′⟩, que não terá estados inacessíveis.

Vamos construir iterativamente o conjunto dos estados acessíveis. Começamos com o conjunto S0 = {q0}, porque o estado inicial é certamente acessível. Construímos o conjunto seguinte assim:

Si={r|δ(q,a)=r para algum q∈Si−1,a∈Σ}∪Si−1

Em palavras, o conjunto S0 é sempre dado; construímos o conjunto S1 tomando todos os estados do conjunto S0 e descobrindo para onde levam as transições, para todos os símbolos de Σ. Unimos esses estados com o conjunto original de estados S0. Pelo mesmo procedimento obtemos o conjunto S2 e os seguintes. Evidentemente, valerá Si − 1 ⊆ Si.

O conjunto dos estados acessíveis pode então ser obtido assim:

⋃i=1∞Si

Pode parecer estranho que tentemos unir infinitos conjuntos Si, mas o autômato contém apenas um número finito de estados. Isso significa que, em algum momento, os conjuntos Sj e Sj + 1 e todos os seguintes serão iguais, de modo que, mesmo após a união de infinitos conjuntos, podemos obter um conjunto finito de estados.

Voltemos ao autômato

e vamos tentar encontrar o conjunto dos estados acessíveis. Começamos estabelecendo a igualdade básica

S0={q0}

Agora calculamos o conjunto S1. Precisamos encontrar todas as transições do estado q0 e acrescentar seus estados de destino ao conjunto S0. Como valem q0 → a q1 e q0 → bq2, o conjunto S1 conterá a mais os estados q1 e q2:

S1={q0,q1,q2}

Em seguida construímos o conjunto S2. Vemos para onde podemos ir a partir dos estados q0, q1, q2. O único estado novo é q5, ao qual podemos chegar a partir do estado q1:

S2={q0,q1,q2,q5}

Depois construímos o conjunto S3. Podemos chegar a algum estado novo a partir dos estados q0, q1, q2, q5? Não podemos, então o conjunto S3 conterá os mesmos elementos que S2:

S3={q0,q1,q2,q5}

Como S2 = S3, também S3 = S4 = S5 = … Se unirmos todos os Si, obtemos o conjunto S2, porque nenhum outro elemento será acrescentado a nenhum dos conjuntos seguintes.

O conjunto dos estados acessíveis do autômato é, assim, igual a {q0, q1, q2, q5}. Obtemos os estados inacessíveis por uma simples diferença de conjuntos:

Q∖⋃i=1∞Si

O conjunto dos estados inacessíveis do nosso autômato é {q3, q4}. Removemos do autômato A todos os estados inacessíveis e todas as transições que continham algum estado inacessível. Ou seja, definimos o autômato A′ = ⟨Q′, Σ, δ′, q0, F′⟩ sem estados inacessíveis, equivalente ao autômato A = ⟨Q, Σ, δ, q0, F⟩, como:

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
  • F′=F∩Q′=F∩⋃i=1∞Si

Fontes

Capítulos: Estados inacessíveis, Estados inúteis, Minimização de autômatos