Минимизиране на автомат

Под минимизиране на автомат разбираме намирането на еквивалентен автомат, който съдържа минимално възможния брой състояния. Дори автомат, който не съдържа никакво излишно състояние, може да бъде опростен допълнително.

Пример

Да вземем този автомат:

Автоматът приема само думите 01 и 11. При това е очевидно, че съществува по-прост автомат с три състояния, който приема същия език. Състоянията q₁ и q₂ могат да се слеят в едно ново състояние {q₁, q₂} и преходите, които водеха към състоянията q₁ или q₂, ще водят към новото състояние, същото важи и за преходите, излизащи от q₁ и q₂. Получаваме този автомат:

Този автомат очевидно приема същия език като предишния, но има по-малко състояния.

Еквивалентност на състояния

Нека имаме автомата A = ⟨Q, Σ, δ, q₀, F⟩. Определяме езика на състоянието q ∈ Q, който означаваме с L(q), като

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

Т.е. променяме началното състояние на автомата A от q₀ на q и пресмятаме езика, приеман от този автомат. С други думи, в езика L(q) са всички думи w, такива че в автомата A от състоянието q с думата w стигаме до крайно състояние на автомата. Ако се върнем към предишния автомат, L(q₁) = {1}.

Казваме, че две различни състояния q₁ и q₂ са еквивалентни, ако

$L (q_{1}) = L (q_{2})$

Какво означава това? Ако състоянията q₁, q₂ са еквивалентни, то ако ги направим начални състояния на автомата, те ще пораждат един и същ език. С други думи: ако автоматът стигне до конфигурация ⟨q₁, w⟩ и ⟨q₂, w⟩, то трябва и в двата случая да приеме, или и в двата случая да отхвърли.

Ако се върнем към предишния автомат: състоянията q₁ и q₂ са еквивалентни, защото ако сме в състоянието q₁, можем да приемем входната дума само ако непрочетената част от думата е равна на 1. Същото е, ако сме в състоянието q₂.

При минимизирането на автомат целта е да намерим еквивалентните състояния и да ги премахнем, като ги слеем в едно ново състояние, както направихме в горния пример.

Как да намерим еквивалентните състояния

Кои състояния със сигурност няма да са еквивалентни? Ако вземем крайно и неприемащо състояние, те със сигурност няма да са еквивалентни, защото езикът на крайното състояние е различен от езика на неприемащото състояние — крайното състояние със сигурност приема думата ε, неприемащото — не. Метода веднага ще покажем на пример. Нека имаме този автомат:

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

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Сега съставяме таблица на преходите и запазваме информацията за групите S₁ и S₂:

$\begin{array}{ccccc} група & състояние & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Сега променяме таблицата така, че вместо да е записано директно в кои състояния отиваме за даден символ, записваме само групата, в която преминаваме. Например от състоянието q₃ за 0 стигаме до състоянието q₅, което е в групата S₂. Вместо q₅ записваме в таблицата S₂:

$\begin{array}{ccccc} група & състояние & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Сега разделяме двете групи допълнително. В една и съща група слагаме състоянията, които за всички символи преминават в едни и същи групи. Например състоянията q₃ и q₆ няма да са в една група, защото нито за 0, нито за 1 не отиват в една и съща група. Обратно, състоянията q₁ и q₂ ще са в една група, защото и двете състояния нямат преход за 0 и двете за 1 отиват в групата S₁. Създаваме така нови групи:

$\begin{array}{ccccc} група & състояние & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Във всяка група имаме еднакви преходи. Новообразуваните групи номерираме и отново определяме в коя от тези нови групи сочат състоянията:

$\begin{array}{ccccc} група & състояние & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

Сега трябва отново да разделим групите. Виждаме обаче, че вече не можем да извършим ново разделяне, бихме получили същите групи — защото състоянията q₁ и q₂ имат еднакви преходи по отношение на групите, но вече са в една група и никое друго състояние в групата S₄ няма. Алгоритъмът за намиране на еквивалентни състояния е стигнал до края. От всяка група ни е достатъчно да изберем по едно състояние, останалите изтриваме и всички преходи, които са водели към изтритите състояния, ще водят към онова едно състояние, което сме избрали.

Можем например да оставим в новия автомат състоянията q₃, q₆, q₀, q₁, q₄, а състоянията q₂ и q₅ да премахнем. Всички преходи, които са водели към q₂, сега ще водят към q₁, а всички преходи, които са водели към q₅, ще водят към q₄:

Стъпки при минимизиране на автомат

Премахваме недостижимите състояния,
премахваме излишните състояния,
премахваме еквивалентните състояния.

Източници

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

« Предишна: Излишни състояния

Следваща: Затвореност на регулярните езици »