§ 9.5. Понятия об эквивалентности, отображении и минимизации последовательностных машин

В предыдущих параграфах рассматривался вопросов эквивалентности отдельных состояний; в этом и следующих параграфах рассматривается вопрос об эквивалентности -машин.

Две П-машины S и G называются эквивалентными относительно L тогда и только тогда, когда для каждого состояния машины S существует по крайней мере одно эквивалентное относительно L состояние машины G, и для каждого состояния машины G существует по крайней мере одно эквивалентное относительно L состояние машины .

Из определения видно, что в этом случае любая входная последовательность из L должна быть допустима как для машины S, так и для машины G. Если множество всех допустимых для машины S последовательностей обозначить , а аналогичное множество для машины G — через , то множество L должно удовлетворять условию

В том случае, когда L=Е (т. е. L содежит все возможные последовательности), мы будем говорить, что машины S и G просто эквивалентны. В этом случае .

Условимся говорить, что машина S отображается на машину G относительно множества L (или машина G отображает машину S относительно множества L) тогда и только тогда, когда для каждого состояния машины S существует по крайней мере одно эквивалентное относительно состояние машины G. Если L=Е, то мы будем говорить просто об отображении машины S на машину .

Из определения отображения и. эквивалентности легко можно вывести следующее свойство: если машина S отображается на машину G относительно L, и машина G отображается на машину относительно того же L, то S и G являются эквивалентными относительно L машинами.

Соотношение эквивалентности машин S и G обозначается , а соотношение отображения машины на машину G обозначается .

В смысле переработки входных последовательностей символов в выходные последовательности эквивалентные машины не отличаются друг от друга.

Если машина отображается (или отображается относительно L) на машину G, то это практически означает, что машина G может заменить машину (но не наоборот).

Рассмотрим две эквивалентные П-машины . Пусть состояния этих машин разбиты на группы эквивалентных состояний. Рассмотрим какую-либо группу эквивалентных состояний машины и выберем произвольное состояние в этой группе. В машине найдется некоторое состояние , эквивалентное . Пусть состояние принадлежит группе эквивалентных состояний машины . Тогда любые два состояния, первое из которых принадлежит группе машины а второе — группе машины , эквивалентны. Вместе с тем ни одно из состояний группы машины не эквивалентно ни одному из состояний группы машины при . Поэтому каждой группе эквивалентных состояний машины соответствует одна и только одна группа эквивалентных состояний машины .

В силу симметрии соотношения эквивалентности машин (из следует ), справедливо и обратное утверждение, что каждой группе эквивалентных состояний машины соответствует одна и только одна группа эквивалентных состояний машины . Поэтому число групп эквивалентных состояний в эквивалентных машинах одинаково, а сами машины отличаются лишь количеством состояний в соответствующих группах.

Если заданы две машины S и G, из которых вторая отображает первую (S с G), то соответствие между группами эквивалентных состояний не является взаимно однозначным: можно утверждать лишь, что каждой группе эквивалентных состояний машины S соответствует одна и только одна группа эквивалентных состояний машины G, но не наоборот. Поэтому число групп эквивалентных состояний машины G может быть больше числа групп машины S: машины S и G могут отличаться, таким образом, не только количеством состояний в каждой группе, но и числом групп.

Все сказанное здесь о соотношении числа групп эквивалентных состояний для эквивалентных и отображающихся машин остается справедливым, если рассматривать эквивалентность и отображение относительно множества входных последовательностей L, ограниченного «в себе».

Введем теперь понятие о минимизации П-машины. Пусть задана -машина S. Под процессом минимизации П-машины S относительно множества L допустимых последовательностей будем понимать отыскание некоторой другой П-машины G, удовлетворяющей следующим двум условиям:

1) П-машина G отображает относительно множества .

2) Не существует никакой другой Я-машины, отображающей S относительно L с числрм состояний, меньшим числа состояний машины .

Последовательностная машина G, удовлетворяющая этим требованиям, называется минимальной для S относительно .

Заметим, что если существует алгоритм распознавания состояний, эквивалентных относительно множества допустимых последовательностей L, то в принципе существует тривиальный алгоритм минимизации относительно L. Действительно, если машина S имеет , то минимальная для S машина G имеет число состояний, не большее чем k. В принципе возможен перебор всех машин (а их конечное число, с числом состояний, не большим к, а наличие алгоритма распознавания эквивалентных относительно L состояний позволяет проверить, отображает ли каждая из перебираемых машин машину .

Разумеется, такой тривиальный алгоритм не имеет практического значения, поэтому возникает задача нахождения алгоритмов минимизации, удобных для практического использования. Такой алгоритм найден пока лишь для случая, когда допустимы все входные последовательности. Рассмотрению этого случая посвящен следующий параграф.