Сб. Июн 15th, 2024

Пусть имеется конечный автомат, данный таблицей:

На базе ее составим другую таблицу, клеточки которой будут соответствовать всем разным парам qiqj (ij), заполнив ее согласно последующим правилам:

  • если два состояния qi и qj неэквивалентны (т.е. для какого-нибудь значения входного знака х значения на выходе различаются), то соответственная клеточка зачеркивается;
  • если в состояниях qi и qj для каждого х значения на выходе схожи, то в клеточки записываются все пары состояний qvqw (vw), хорошие от qiqj, в которые автомат может перейти из qi и qj при подаче 1-го и такого же входного знака.

Согласно первому правилу зачеркнутой оказалась, к примеру, клеточка, соответственная паре q1q2, так как при х = 0 на выходе выдаются различные значения (1 и 0). По второму правилу, к примеру для пары q5q6 следует записать пару q2q5 из последующих суждений: у q5 и q6 все выходные знаки схожи при схожих входных; х = 0 приводит к начальной паре q5q6; х = 1 приводит к паре схожих состояний q6q6.

Схожим образом анализируются другие сочетания.

В конце концов, следующими преобразованиями вычеркиваются клеточки, в каких находятся пары, надлежащие уже зачеркнутым ранее клеточкам. К примеру, следует зачеркнуть клеточку для пары q1q4, так как в ней содержится q3q6, также q3q4, потому что в ней есть q2q3. Потом опять необходимо зачеркнуть все клеточки, которые содержат пары, надлежащие вычеркнутым клеточкам. Процедура должна длиться до того времени, пока не сформируется таблица, в какой нельзя вычеркнуть ни одной из оставшихся клеток. Для рассматриваемого примера эти клеточки выделены жирной рамкой. Можно обосновать, что оставшиеся не вычеркнутыми клеточки соответствуют всем парам эквивалентных состояний. Это q1q3, q2q5, q2q6 и q5q6. Классы эквивалентности образуются состояниями, которые попарно эквивалентны. В данном случае это {q1,q3} и {q2, q5, q6}. Состояния, не вошедшие в эти классы, эквивалентны только для себя и образуют собственные классы эквивалентности; в рассматриваемом примере это {q4}. Таким образом, классы эквивалентности оказались выделенными.

После выделения классов эквивалентности состояний для автомата М можно выстроить эквивалентный ему автомат M‘. В качестве входного и выходного алфавитов для М‘ возьмем надлежащие алфавиты М, а каждому классу эквивалентных состояний М сравним одно состояние М’. Для рассмотренного выше примера можно принять (q1)’ ↔ {q1, q3}, (q2)’ ↔ {q2, q5, q6}, (q3) ↔ {q4}.

Совсем получаем таблицу нового автомата М’.

Можно обосновать последующую аксиому*:

* Интересующихся подтверждением можно адресовать к книжке Л.А. Шоломова [48, с.125-126].

От content

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *