1. Множество L допустимых входных последовательностей содержит все возможные последовательности, т. е. L=E

Построение и минимизацию П-машины, работающей как заданный автомат А, рассмотрим на примере. Пусть таблица заданного автомата А имеет вид табл. 9.1.

Таблица 9.1

В § 9.6 было установлено, что при отсутствии ограничений на входные последовательности минимальная

П-машина для заданной машины N находится в классе машин, эквивалентных N, и ни одно ее состояние не имеет эквивалентных. Следовательно, в рассматриваемом частном случае искомая минимальная машина должна быть эквивалентна заданному автомату А.

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

Соединим кружки стрелками в соответствии с заданной таблицей автомата.

Над каждой стрелкой в качестве первого символа указывается индекс , соответствующий этой стрелке по таблице автомата, а в качестве второго символа — номер кружка, к которому подходит стрелка. Надписи на рис. 9.9 указаны в соответствии .

Рис. 9.9.

Будем трактовать теперь построенный граф (рис. 9.9) как диаграмму состояний некоторой П-машины. Для этого комер кружка заменим символом , а надпись на стрелке вида — парой символов такая замена для графа рис. 9.9 показана на рис. 9.10.

Рис. 9.10.

Построим теперь матрицу соединений П-машины, диаграмма состояний которой изображена на рис. 9.10:

В соответствии с описанным способом построения диаграммы состояний в матрице соединений все ненулевые элементы любого столбца имеют одинаковые вторые индексы, совпадающие с номером столбца.

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

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

Горизонтальные линии следует провести между второй и третьей и между третьей и четвертой строками. После этого матрица С оказывается разбитой на три -матрицы. Каждая -матрица этого разбиения обладает следующим свойством: в каждом столбце стоят либо нули, либо совпадающие пары. Так, в верхней -матрице (состоящей из двух строк), в первом столбце стоят нули, во втором столбце стоят пары , в третьем — , в четвертом — . Это свойство есть следствие отмеченного выше свойства матрицы С. В самом деле, если вторые цифры пар каждого столбца во всей матрице С одинаковы, то в строках этой матрицы, содержащих лишь одинаковые пары (образующие -матрицу), будут совпадать и. первые цифры пар каждого столбца.

Но если так, то для выявления групп эквивалентных состояний достаточно разбить матрицу С на -матрицы лишь горизонтальными линиями; ввиду совпадения элементов в столбцах каждой -матрицы проведение симметричных вертикальных линий никогда не сможет «испортить» разбиения.

Это свойство означает следующее: разбиение состояний Я-мащины, имеющей матрицу состояний С, на группы состояний и группы состояний, эквивалентных относительно множества , содержащего все последовательности длины , совпадают. Поэтому для выявления всех групп эквивалентных состояний достаточно построить разбиение на группы состояний, эквивалентных относительно множества что и достигается путем разбиения матрицы С горизонтальными линиями на -матрицы.

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

а ее диаграмма состояний показана на рис. 9.11.

Рис. 9.11.

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

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

Рис. 9.12.

Построив диаграмму состояний, можно по ней выписать таблицы автомата и преобразователя , которые образуют по схеме рис. 9.12 минимальную П-машину, работающую как автомат А. В нашем примере (рис 9.10) эти таблицы имеют вид табл. 9.2 и 9.3. Из описанного на примере способа построения табл. 9.2 и 9.3 видно, что как в этом примере, так и в общем случае, таблица автомата нашем примере табл. 9.2) могла бы быть получена и непосредственно по заданной таблице автомата А (в нашем примере табл. 9.1).

Таблица 9.2

Таблица 9.3

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

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

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