Минимизация детерминированного автомата

Из двух детерминированных автоматов, допускающих один и тот же язык, меньше памяти (при реализации) занимает тот, у которого меньше состояний. Число состояний автомата можно уменьшить, удалив состояния, не используемые при анализе допустимых цепочек. Для этого достаточно преобразовать соответствующую А-грамматику к приведённому виду.

Дальнейшая минимизация детерминированного автомата основана на выявлении эквивалентных состояний. Состояния автомата q и q ' называются эквивалентными, если в соответствующей А-грамматике L (q) = L (q '). Неэквивалентность q и q ' означает, что существует цепочка, на которой из одного состояния достижимо заключительное состояние, а из другого - нет. Для детерминированного автомата можно указать алгоритм нахождения эквивалентных состояний. Дальше детерминированный автомат будем просто называть автоматом.

Назовем автомат полным, если его функция перехода тотальна, т.е. определена на всех парах (q, a) (в предыдущем примере автомат полон). Полный автомат любую цепочку прочитывает до конца и останавливается либо в заключительном состоянии, либо в незаключительном.. Поэтому для него неэквивалентность q и q ' означает, что для некоторой цепочки a Î T ^* q - a ® q ₁, q ₁Î F, и q '- a ® q ₂, q ₂Ï F. Говорят, что такая цепочка a различает состояния q и q '.

Отсюда следует

У т в е р ж д е н и е 4.1. Для полного автомата отношение ne (q, q ') неэквивалентности q и q ' определяется условиями:

a. ne (q, q '), если q Î F, а q 'Ï F, или q Ï F, а q 'Î F, т.е. цепочка e различает состояния q и q ';

b. ne (q, q '), если a различает состояния t (q, a) и t (q ', a) для некоторого a (тогда aa различает состояния q и q ').



Все остальные пары (q, q ') состояний полного автомата являются парами эквивалентных состояний.

Пример 4.4. Для полного детерминированного автомата в примере 4.3 (рис. справа) из условия a следует неэквивалентность q и q ', если q Î F = { q ₁₃, q ₂₃, q ₁₂₃} и q 'Î Q \ F = { q ₀, q ₁, q ₂, q ₁₂}. Отсюда, по условию b, следует неэквивалентность всех пар из Q \ F и ничего не следует для пар состояний из F, т.е. все состояния из F эквивалентны между собой.


У т в е р ж д е н и е 4.2. Для каждого неполного автомата можно построить эквивалентный полный автомат с сохранением всех языков L (q).

Доказательство. Неполный автомат можно сделать полным, добавив новое незаключительное состояние r с правилами (r, a) ® r для всех a Î T, и добавив для каждой пары (q, a), q ¹ r, для которой не было правила, новое правило (q, a) ® r. Поскольку из r достижимо только r и это состояние незаключительное, то оно непродуктивное. Следовательно, сохраняются все языки L (q). Детерминированность при этом также сохраняется.


У т в е р ж д е н и е 4.3. Проблема эквивалентности состояний детерминированного автомата алгоритмически разрешима.

Доказательство. Для заданного автомата сначала можно построить эквивалентный полный автомат, затем для полного автомата найти все пары неэквивалентных состояний, остальные пары состояний объявить эквивалентными. Алгоритм построения множества пар неэквивалентных состояний и его обоснование следует из утверждения 4.1.

Алгоритм 4.1 (построение множества пар неэквивалентных состояний). Алгоритм строит отношение неэквивалентности ne:

1. ne ⁽⁰⁾ = {(q, q ') | q Î F, q 'Ï F, или q Ï F, q 'Î F };

2. ne ^{(i +1)} = ne ⁽ⁱ⁾ È {(q, q ') | ne ⁽ⁱ⁾(t (q, a), t (q ', a)) для некоторого a }, i > 0.

Алгоритм завершается, когда ne ^{(i +1)} = ne ⁽ⁱ⁾, т.е. ne = ne ⁽ⁱ⁾. Это происходит за конечное число шагов, т.к. число пар конечно.


Т е о р е м а 4.3. Проблема эквивалентности А-грамматик алгоритмически разрешима.

Доказательство. Следует из предыдущих результатов и того, что утверждение 4.3 и его доказательство справедливо и для состояний разных автоматов.


Следующее преобразование называется минимизацией полного детерминированного конечного автомата. Оно состоит в "склеивании" (т.е. в одинаковом переименовании) всех эквивалентных друг другу состояний и в последующем преобразовании автомата к приведенному виду (в смысле соответствующей грамматики). Очевидно, что минимизация - эквивалентное преобразование, после которого у автомата все различные состояния оказываются неэквивалентными.

Пример 4.5. Для полного автомата в примере 4.3 (рис. справа) в примере 4.4 было показано, что его заключительные состояния q ₁₃, q ₂₃, q ₁₂₃ эквивалентны. Склеив их и переименовав в q ₃, получим приведённый автомат с диаграммой



То, что получаемый таким образом автомат действительно минимален по числу состояний, доказывает следующая

Т е о р е м а 4.4. Пусть A = (Q, T, t, q ₀, F) и A ' = (Q ', T, t ', q ₀', F ') - эквивалентные детерминированные автоматы, причем A - приведенный автомат с попарно неэквивалентными состояниями, Q Ç Q ' = Æ. Тогда у A состояний не больше, чем у A '.

Доказательство. Покажем, что для каждого состояния из Q в Q ' есть эквивалентное ему состояние. Эти состояния из Q ' также попарно неэквивалентны, откуда следует, что они попарно различны и, значит, | Q | £ | Q '|.

По условию, L (q ₀) = L (q ₀'). Далее, если L (q) = L (q ') для q Î Q и q 'Î Q ', то в силу детерминированности автоматов и продуктивности всех состояний A (т.к. он приведенный) из t (q, a) = q ₁ следует, что t '(q ', a) = q ₁' и L (q ₁) = L (q ₁') для q ₁Î Q и q ₁'Î Q '. Так как A приведенный и, следовательно, все его состояния достижимы из q ₀, то таким способом, начиная с q = q ₀, можно найти для каждого q Î Q эквивалентное ему состояние q 'Î Q '.


Замечание. Из доказательства следует, что диаграммы любых двух эквивалентных минимальных детерминированных автоматов изоморфны.


В качестве дополнительного результата докажем следующее утверждение.

Т е о р е м а 4.5.. Класс языков Reg (T) замкнут относительно дополнения, т.е. из L Î Reg (T) следует, что и T ^* \ L Î Reg (T).

Доказательство. Поскольку, как следует из предыдущего, регулярный язык L допускается полным детерминированным автоматом A = (Q, T, t, q ₀, F), то T ^* \ L допускается автоматом A ' = (Q, T, t, q ₀, Q \ F), т.к. каждую цепочку автомат A прочитывает до конца.


Дата добавления: 2014-01-07