) Понятие «состояние», как основное при описании систем, было впервые введено в 1936 г. Тьюрингом (А. М. Turing, On Computable Numbers with an Application to the Entscheidungpro-blem, Proc. London Math. Soc, ser. 2, vol. 42, pp. 230-265, 1936- 1937). Позже это понятие было использовано Шенноном в его основополагающей работе по теории информации (С. Е. S h е п-поп, А Mathematical Theory of Communication, Bell System Tech. J., vol. 27, pp. 379-423, 623-656, 1948). Еще позднее понятие «состояние» было вновь введено Хаффменом (D. А. Huffman, The Synthesis of Sequential Switching Networks, J. Franklin Inst., vol. 257, pp. 161-190, 275-303, 1954), Клини (S. C. Kleene, Representation 0 Events in Nerve and Finite Automata, «Automata Studies», pp. 3-41, Princeton University Press, Princeton, N. Y., 1956. Русский перевод: С. К. Клини, Представление событий в нервных сетях и конечных автоматах. В сборнике «Автоматы» под редакцией К. Э. Шеннона и Дж. Маккарти, ИЛ, М., 1956) и Муром (Е. F. Moor е, Qedanken - Experiments on Sequential Machines, «Automata Stu-dies», pp. 129-153, Princeton University Press, Princeton, N. Y., 1956. Русский перевод: Э. Ф. М у р, Умозрительные эксперименты с по-следовательностными машинами. В сборнике «Автоматы» под редакцией К. Э. Шеннона и Дж. Маккарти, ИЛ, М., 1956), после чего оно было принято как одно из основных понятий теории дискретных систем.

определить выходной символ в данный тактовый момент и состояние в следующий тактовый момент i).

В качестве примера рассмотрим игру, в которой монета повторно подбрасывается и производятся отметки при появлении каждого первого герба в серии гербов и каждой, исключая первые две, цифры в серии цифр. В этом примере системой является игра, синхронизирующим источником - игрок, а синхронизирующим сигналом - операция бросания монеты; входной переменной является сторона монеты, выходной переменной - отметка при броске. Тогда входной алфавит будет {цифра, герб}, а выходной-{отметка, нет отметки}. Для определения множества состояний находят такое множество условий (которые могут быть выражены словесно, символами, в числовом виде или в какой-нибудь другой удобной форме), чтобы по известному в настоящий момент условию и стороне монеты однозначно определялось наличие или отсутствие отметки в настоящий момент и условие в следующий. Из описания игры можно установить, что для того, чтобы предсказать отметку, необходимо знать стороны монеты в настоящий момент и в два предыдущих. Временно примем следующее множество состояний {появление первой цифры.

1.6] ОПРЕДЕЛЕНИЕ ОСНОВНОЙ МОДЕЛИ 21

появление двух цифр, появление первого герба], где «появление первой цифры» - состошие системы, когда цифра выпала первый раз после герба, «появление двух цифр» - состояние системы, когда цифра выпала после цифры, и «появление первого герба» - состояние системы, когда герб выпал после герба или по:ле цифры. Отметка производится каждый раз, когда система находится в состоянии «появление двух цифр» и входом является цифра или когда система находится в состоянии, отличном от состояния «появление первого герба», и входом является герб. Если состояние в настоящий момент - «появление первой цифры» или «появление двух цифр», то состояние в следующий момент будет «появление двух цифр», если входом является цифра, и «появление первого герба», если входом является герб. Если состояние в настоящий момент - «появление первого герба», то состояние в следующий момент будет «появление первой цифры», если входом является цифра, и «появление первого герба», если входом является герб. Таким образом, подтверждается, что выбранное множество состояний отвечает предъявляемым требованиям, так как по известному состоянию системы и входу в настоящий момент может быть определен выход в настоящий момент и состояние в следующий.

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

1.6. Определение основной модели

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

Определение 1.1. Конечным автоматом М называется синхронная система с конечным входным алфавитом Х =

~ 1\ I2.....1р], с конечным выходным алфавитом Z =

~ 2..... tJ, С конечным множеством состояний

) Определение 1.1 задает конечный автомат Мили. (Прим. перев.)

) Такие автоматы называются также автоматами без памяти или комбинационными устройствами. (Прим. ред.)

5= {О], 02.....а„) и двумя характеристическими функциями и /,:

= v> (1-5)

5v+l=A(-»v. (Ь6)

где дГу, и - соответственно входной символ, выходной символ и состояние автомата М в момент (v= 1, 2, ...))•

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

Особый тип конечного автомата получается при условии,

Л = К, s,) = f,{x). (1.7)

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

/.(v Sv)=/.(v) (1-8)

1.7. Примеры конечных автоматов

Для иллюстрации разнообразия ситуаций, моделью которых может служить конечный автомат, приведем несколько примеров. Для каждого примера будут указаны: входной алфавит X, выходной алфавит Z и подходящее множество состояний 5. Названия состояний системы будут выбираться таким образом, чтобы передать условия, определяющие эти состояния. Для каждого примера будет дано его словесное описание, которое будет служить основой при выборе множества состояний.