младший, т.е. s0->sj->s2-> s3->s0->sj... . Входным алфавитом автомата Мявляется сигнал с двумя устойчивыми состояниями, которые обозначим 0-отсутствие поворота и 1-поворот на четверть оборота - переход в следующее положение (состояние), т.е. х={0,1}. В качестве выходного алфавита примем сигналы, формируемые датчиками положений револьверной головки, совпадающие с номерами положений Si, к которым движется головка из рассматриваемого состояния под воздействием входной переменной, т.е. при движении к s0,y=0, к s1 y=l ит.д. Сучетомсказанного таблицы переходов и выходов примут вид соответственно таблице 3.1 и таблице 3.2

Таблица 3.1Таблица 3.2

Таблица переходовТаблица выходов

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

Так, таблица 3.3 является общей таблицей переходов автомата М и объединяет таблицу 3.1 и таблицу 3.2

Таблица 3.3

Общая таблица переходов

3.4. ЗАДАНИЕ КОНЕЧНОГО АВТОМАТА В ВИДЕ ГРАФА

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

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

На рис.3.2 изображен граф, построенный в соответствии с вышеописанной работой револьверной головки (см. таблицу 3.3).

Рис.3.2. Граф автомата-револьверной головки

3.5. МАТРИЧНЫЙ СПОСОБ ЗАДАНИЯ КОНЕЧНОГО АВТОМАТА

Матрица соединений автомата М (или матрица переходов ) представляет собой квадратную таблицу, в которой номера строк и столбцов соответствуют номерам состояний. Клетка матрицы на пересечении i-й строки и j-го столбца заполняются дизъюнкцией пар "вход/выход" (х/у), которая приписана дуге графа, исходящей из i-u j-ю вершину. При отсутствии такой дуги клетка заполняется нулем или остается свободной. Графу, изображенному на рис.3.2, соответствует матрица соединений, представленная таблицей 3.4 .

Таблица 3.4

Матрица соединения автомата

О

М =

>l

3.6. АВТОМАТЫ МУРА И МИЛИ

Данное выше определение (3.1) конечного автомата характеризует автомат Мили.

Автомат, у которого функция выходов v(x,s)=v(s) не зависит от входных переменных, называется автоматом Мура [З].

Граф автомата Мура имеет несколько другой вид, чем граф автомата

Мили. Поскольку в этом случае выходная буква однозначно определяется

состоянием, ее помещают в вершине графа, вместе с обозначениями его состояния,

О

О

So/0

S3/3

1

\S,/1

,S2/2j

Рис.3.3. Граф автомата Мура

О

О

а стрелкам приписывают значение не пар "вход-выход", а только входных символов. На рис.3.3 изображен граф автомата Мура, описывающий работу ранее рассмотренной револьверной головки.

Автоматы Мура и Мили могут быть преобразованы один в другой.

3.7. НЕКОТОРЫЕ КЛАССЫ КОНЕЧНЫХ АВТОМАТОВ

Автомат с выделенным (начальным) состоянием so называется инициальным. Функционирование инициального автомата M={X,S,Y,(p,v,so,} состоит из троек слов (a,fry), таких, что при некотором hе{1,2,3,...} выполняется

а = х(1)...х(т), р = s(l)...s(m +1), у = у(1)...у(т) ,(3.5)

где x(i), s(i), y(i) - значение букв входного и выходного алфавита и алфавита внутренних состояний в текущий такт работы автомата, причем имеет место система отношений

s( 1) = s0

s(h + 1) = y/(s(h),x(h)) > y(h)=v(s(h),x(h)) J ,

называемая системой канонических уравнений автомата М [З].

Автомат М называется автоматом без памяти, если функция выходов v(x, s)=v(x) не зависит от внутренних состояний автомата М. Вэтомслучае автомат М реализует в каждый момент времени отображение слова х вслово у без учета информации, поступившей на вход автомата в предыдущие моменты времени.