Пусть имеется конечный автомат, данный таблицей:
На базе ее составим другую таблицу, клеточки которой будут соответствовать всем разным парам qiqj (i ≠ j), заполнив ее согласно последующим правилам:
Согласно первому правилу зачеркнутой оказалась, к примеру, клеточка, соответственная паре 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].
Если основа оригинала (карты пли плана) прозрачна, то копию можно снять при помощи стола со…
Определение координат точки. Пусть точка А (рис. 32) находится в квадрате, абсциссы и ординаты вершин…
Рельефом местности называется совокупность неровностей физической поверхности земли. В зависимости от характера рельефа местность делят…
Для обозначения на планах и картах различных предметов местности, применяются специально разработанные условные знаки. Для обличения…
В инженерной геодезии чаще всего пользуются топографическими картами. Их составляют в масштабах 1:10000, 1:25000, 1:50000…