Излишни състояния

Един краен автомат може да има състояния, от които е невъзможно да се стигне до крайно състояние и които затова са ненужни. Такива състояния наричаме излишни състояния. Обикновено искаме да ги премахнем, защото само излишно усложняват целия автомат.

Пример за излишни състояния

Нека имаме този краен автомат:

Виждаме, че щом попаднем в състоянията q₄ или q₅, никога вече няма да успеем да стигнем до някое от крайните състояния q₁ или q₂. Такива състояния са излишни и можем просто да ги премахнем, с което ще получим нов автомат, който обаче ще е еквивалентен; ще приема същия език. След изтриването на излишните състояния автоматът би изглеждал така:

Той би приемал същия език. Има обаче моменти, когато е удобно да имаме някои излишни състояния — например когато построяваме тотален автомат.

Определение на излишно състояние

Нека имаме краен автомат A = ⟨Q, Σ, δ, q₀, F⟩. Казваме, че състоянието q ∈ Q е излишно, ако не съществува никаква дума w ∈ Σ^∗ и никакво състояние q_f ∈ F, такива че

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

Как да премахнем излишните състояния

Предполагаме, че на входа имаме автомат A = ⟨Q, Σ, δ, q₀, F⟩, който вече е без недостижими състояния. Постепенно ще намираме състоянията, които водят до крайни състояния, после състоянията, които водят до състояния, които водят до крайни състояния, и така нататък. По този начин получаваме множеството на всички състояния, които не са излишни. В началото полагаме S₀ = F. Ще построяваме следващите множества S_i за i ∈ ℕ по това правило:

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

Полученото множество на всички състояния, които не са излишни, можем да изразим така:

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

А множеството на излишните състояния като

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

С други думи: ако S_i = S_{i + 1}, то множеството Q ∖ S_i съдържа излишните състояния. Метода ще илюстрираме на този автомат:

Първо полагаме равенството S₀ = {q₁, q₂}. После построяваме множеството S₁, като към множеството S₀ добавим всички състояния, които водят до някое от състоянията в множеството S₀. Добавяме следователно състоянията q₀ и q₃, защото от q₀ води преход към q₁, а от q₃ води преход към q₂. Получаваме S₁ = {q₀, q₁, q₂, q₃}. Тъй като S₀ ≠ S₁, продължаваме нататък.

Построяваме множеството S₂. Търсим всички състояния, от които може да се стигне до S₁ и които още не са в S₁. Това е едно-единствено състояние, q₆, от което може да се стигне до състоянието q₃. Получаваме S₂ = {q₀, q₁, q₂, q₃, q₆}. Тъй като S₁ ≠ S₂, продължаваме нататък.

Построяваме множеството S₃. Съществува ли ново състояние, от което може да се стигне до някое от състоянията в S₂? Не съществува, от състоянията q₄ и q₅ не може да се стигне до нито едно от състоянията в S₂, а останалите състояния вече са в S₂. Следователно S₃ = {q₀, q₁, q₂, q₃, q₆}. Тъй като S₂ = S₃, алгоритъмът свършва и множеството S₂ е множеството на състоянията, които не са излишни. Множеството {q₄, q₅} е множеството на състоянията, които са излишни.

Формално нов еквивалентен автомат без излишни състояния построяваме така. Имаме автомата A = ⟨Q, Σ, δ, q₀, F⟩ и построяваме към него еквивалентен автомат A′ = ⟨Q′, Σ, δ′, q₀, F⟩ без излишни състояния.

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a), ако δ(q, a) ∈ Q′, иначе δ′(q, a) не е определена

Източници

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