✖

Недостижими състояния

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

Пример за недостижими състояния

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

Виждаме, че каквото и да правим, никога няма да стигнем до състоянието q3, защото към него не води никакъв преход. За състоянието q3 казваме, че е недостижимо. Въпрос — щеше ли състоянието q3 да е достижимо, ако към него водеше някакъв преход от друго състояние? Ако бяхме прокарали ребро от някое от състоянията q0, q1, q2, q5, щеше да е достижимо. Ако добавим още един възел и прокараме преход от него…

…разбира се, и двете състояния q3 и q4 ще са недостижими.

Определение на недостижимо състояние

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

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

Състоянието q ∈ Q е недостижимо, ако не е достижимо.

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

Ако автоматът вече има някакви недостижими състояния, добре е да ги премахнем. Построяваме еквивалентен автомат A′ = ⟨Q′, Σ, δ′, q0, F′⟩, който ще е без недостижими състояния.

Ще построяваме итеративно множеството на достижимите състояния. Започваме с множеството S0 = {q0}, защото началното състояние със сигурност е достижимо. Следващото множество построяваме така:

Si={r|δ(q,a)=r за някое q∈Si−1,a∈Σ}∪Si−1

Казано просто, множеството S0 винаги е дадено, а множеството S1 построяваме така, че вземаме всички състояния от множеството S0 и откриваме къде водят преходите за всички символи от Σ. Тези състояния обединяваме с първоначалното множество от състояния S0. По същия начин намираме множеството S2 и следващите. Очевидно е в сила Si − 1 ⊆ Si.

Множеството на достижимите състояния след това можем да получим така:

⋃i=1∞Si

Може да изглежда странно, че се опитваме да обединим безкрайно много множества Si, но автоматът съдържа само краен брой състояния. Това означава, че в един момент множествата Sj и Sj + 1 и всички следващи ще са еднакви, така че и след обединението на безкрайно много множества можем да получим крайно множество от състояния.

Да се върнем към автомата

и да опитаме да намерим множеството на достижимите състояния. Започваме, като положим основното равенство

S0={q0}

Сега пресмятаме множеството S1. Трябва да намерим всички преходи от състоянието q0 и техните целеви състояния да добавим към множеството S0. Тъй като q0 → a q1 и q0 → bq2, множеството S1 ще съдържа допълнително състоянията q1 и q2:

S1={q0,q1,q2}

След това построяваме множеството S2. Гледаме къде можем да стигнем от състоянията q0, q1, q2. Единственото ново състояние е q5, до което можем да стигнем от състоянието q1:

S2={q0,q1,q2,q5}

След това построяваме множеството S3. Можем ли от състоянията q0, q1, q2, q5 да стигнем до някое ново състояние? Не можем, така че множеството S3 ще съдържа същите елементи като S2:

S3={q0,q1,q2,q5}

Тъй като S2 = S3, то и S3 = S4 = S5 = … Ако обединим всички Si, получаваме множеството S2, защото вече никакъв друг елемент не се добавя в никое следващо множество.

Множеството на достижимите състояния на автомата следователно е равно на {q0, q1, q2, q5}. Недостижимите състояния получаваме чрез обикновена разлика на множества:

Q∖⋃i=1∞Si

Множеството на недостижимите състояния на нашия автомат е {q3, q4}. Премахваме от автомата A всички недостижими състояния и всички преходи, които са съдържали някое недостижимо състояние. Т.е. еквивалентния автомат без недостижими състояния A′ = ⟨Q′, Σ, δ′, q0, F′⟩ на автомата A = ⟨Q, Σ, δ, q0, F⟩ определяме като:

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

Източници

Глави: Недостижими състояния, Излишни състояния, Минимизиране на автомат