§ 3.4. Последовательностные машины

Рис. 3.3.

Рассмотрим систему (рис. 3.3), состоящую из: а) конечного автомата А, преобразующего символы из алфавита в символы из алфавита в соответствии с соотношением (3.5) или , с некоторой заданной функцией F в правой части и б) преобразователя , который мгновенно и однозначно ставит в соответствие каждому символу символ к из некоторого алфавита :

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

то рассматриваемая система, состоящая из автомата А и преобразователя , в целом вновь составит конечный автомат.

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

Пусть, например, алфавит содержит восемь символов, а алфавит — два символа, и преобразователь Ф выдает символ при подводе одного из символов или при . Рассмотрим соотношение (3.5). Пусть функция F в его правой части такова, что после появляется символ , а после появляется символ . В первом случае считывающее устройство зафиксирует

а во втором случае

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

Однако система, представленная на рис. 3.3, также является конечной динамической системой. Мы будем называть ее конечным автоматом с выходным преобразователем или просто конечным, автоматом с выходом. Символы А. называются в этом случае выходными символами (в отличие от — символов состояния), алфавит — выходным алфавитом, а преобразователь — выходным преобразователем.

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

Разумеется, при этом вся П-машина в каждом частном случае может быть или не быть конечным автоматом. Это зависит от вида функции F в соотношениях (3.5) для автомата А и от выбора преобразователя . Но в любом случае система, показанная на рис. 3.4, относится к классу конечных динамических систем.

Рис. 3.4.

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

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

Конечный автомат с выходным преобразователем можно рассматривать как частный случай -машины, у которой функция Ф не зависит от .

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

Условимся называть последовательностную машину машиной типа П — П или типа П — Н в зависимости от того, какого типа автомат она содержит.

Рассмотрим произвольную последовательностную машину типа П — Н:

Исключая из уравнения преобразователя символ , получаем

Введем в рассмотрение символ , заданный на алфавите соотношением

После замены получим

Используя символ в уравнении (3.10) автомата, получаем

т. е. в совокупности получается -машина типа П — П

Таким образом, любая -машина типа П — Н только сменой выходного преобразователя Ф на может быть превращена в -машину типа П — П. Обратное утверждение, в общем случае, неверно. Мы вернемся к нему позже, в § 5.4, после того как будут рассмотрены различные способы задания автомата и -машины и будет введено понятие «сеть».