§ 3.6. Методы записи работы автомата

Символы последовательно «сообщаются» автомату (или -машине) извне и не зависят от его работы. Автомат (или П-машина) перерабатывает символы в символы (или ).

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

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

Рассмотрим теперь таблицу, состоящую из трех строк (номер такта, символ и символ ) и содержащую . сколь угодно большое число столбцов (табл. 3.10).

Таблица 3.10

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

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

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

В любом месте любой ленты какого-либо автомата выделим три символа так, как это показано в табл. 3.10 жирной линией, если этот автомат типа П — П, либо пунктиром, если этот автомат типа П — Н. Ясно, что выделенная так тройка символов является триадой и определяет однуклетку основной таблицы автомата.

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

В предыдущем параграфе мы показали, что автомат как оператор может быть задан конечным упорядоченным множеством триад. Мы видим теперь, что все ленты автомата составлены из триад этого же множества.

Выберем теперь какой-либо алфавит из символов, например , и припишем символы t всем триадам рассматриваемого автомата. Тогда лента может содержать лишь две строки: номер такта и символ (табл. 3.11).

Однако в этой ленте после какой-либо триады, например после , может следовать не любая из триад этого же множества, а лишь «избранные». Действительно, пусть триадой те служит

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

Таблица 3.11

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

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

Таблица 3.1

Полученная таким образом лента (табл. 3.12) также может быть «расщеплена» на триады типа

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

Это множество триад становится упорядоченным тогда и только тогда, когда последовательностная машина в целом является конечным автоматом.

Рассмотрим еще один способ записи работы конечного автомата. Вернемся к диаграмме состояний конечного автомата (рис. 3.7) и рассмотрим на этой диаграмме два кружка. Один из них соответствует символу , а второй — . На рис. 3.10 показана для примера часть диаграммы состояний, содержащая рассматриваемые кружки и, кроме того, еще три кружка . Из состояния можно перейти в состояние за один такт, если символ на входе . Для того чтобы перейти из за два такта, имеются следующие возможности: во время первого такта должно быть либо , а во время второго такта — , либо во время обоих тактов должно быть . Но чтобы перейти из за три такта, можно указать уже девять различных возможностей (табл. 3.13).

Рис. 3.10.

Совершенно аналогично можно выписать все возможные последовательности , которые переводят состояние за q тактов. Назовем любую из этих последовательностей путем длины q от . Условимся записывать каждый путь длины q от в форме последовательности из q символов , а совокупность всех возможных путей — дизъюнкцией таких последовательностей. Так, табл. 3.13 может быть записана в форме

Обозначим дизъюнкцию, соответствующую всем возможным путям длины q от .

Каждая, из дизъюнкций содержит одну или несколько последовательностей. Каждай из последовательностей имеет ровно q элементов , среди которых могут быть и одинаковые.

Таблица 3.13

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

Назовем матрицей путей длины q. Как и в матрице соединений» строки этой матрицы (сверху вниз) и столбцы (слева направо) соответствуют символам . Эти символы записаны слева и над матрицей .

Матрица содержит все пути, ведущие от любого начального состояния к любому конечному состоянию (оно может совпадать с начальным) за q тактов. В связи с тем, что любая последовательность из q символов переводит автомат из любого состояния в то же или иное состояние, в каждой строке матрицы содержатся, и притом по одному разу, все возможные последовательности, которые можно составить из алфавита , выбирая каждый раз по q символов. Так, например, каждая строка матрицы обязательно содержит последовательности

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

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

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

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

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

2. Знаки сложения всюду меняются на знаки дизъюнкций.

3. Знаки умножения определяют операцию приписывания символов .

В качестве примера вернемся к матрице С, выписанной в предыдущем параграфе для диаграммы состояний

рис. 3.7, и возведем ее в квадрат по указанным правилам:

Непосредственно видно, что , т. е. что элементами матрицы служат все возможные пути, которые ведут от одного кружка к другому за два такта в соответствии с диаграммой состояний рис. 3.7. Так, например, элементом первой строки и второго столбца служит Пути ведут за два такта из , и иных путей из в нет (рис. 3.7).

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

Но наличие таких ненулевых элементов в С указывает на то, что из можно за один такт попасть в , а из один такт — в , т. е. на существование путей, ведущих за два такта из .

Таким образом, обнаруженное выше на примере совпадение на самом деле представляет собой правило: квадрат матрицы соединений есть матрица путей за два такта: Образуем теперь матрицу , т. е. умножим на С. Совершенно аналогично убеждаемся, что , т. е. что куб матрицы соединений есть матрица путей за три такта и что вообще матрица путей за q тактов может быть получена возведением в степень q матрицы

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

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

Если требуется перемножить дизъюнкции пар, то надо использовать дистрибутивность операции умножения дизъюнкций, например:

В качестве примера рассмотрим матрицу соединений последовательностной машины с тремя состояниями, имеющей диаграмму состояний, показанную на рис. 3.11.

В результате возведения этой матрицы в квадрат получаем

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

Рис. 3.11.

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

В этом случае под умножением понимается операция приписывания символов, например:

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

В нашем примере матрица имеет вид

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

Продолжая процесс умножения матрицы С на себя, получаем матрицу и находим, таким образом, все входные последовательности, переводящие состояние в состояние да q тактов.