6. Автоматы

6.1. Определение основных понятий

Определение: Конечным автоматом (автоматом) называется система S={A,Q,V,, }, в которой A={a₁,…, a_m}; Q={q₁,…, q_n}; V={v₁,…, v_k} – конечные множества (алфавиты), а : QAQ и : QAV – функции, определяемые на этих множествах.

А называется входным алфавитом, V- выходной алфавит, Q – алфавит состояний,  - функция переходов,  - функция выходов. Если, кроме того, в автомате S выделено одно состояние, называемое начальным (q₁), то такой автомат называется инициальным и обозначается (S,q₁), таким образом, по неинициальному автомату с n состояниями можно n различными способами определить инициальный автомат. Поскольку функции  и  определены на конечных множествах, их можно задавать таблицами. Обычно две таблицы сводятся в одну : QA=QV. Эта таблица называется таблицей автомата или просто автоматной таблицей.

Пример 1: Таблица задает функции переходов и выходов для автомата с алфвитами: A={a₁, a₂, a₃}; Q={q₁, q₂, q₃, q₄}; V={v₁, v₂}

Таблица 20

q\a	a1	a2	A3
q1	q3,v1	q3,v2	q2,v1
q2	q4,v1	q1,v1	q1,v1
q3	q2,v1	q3,v1	q3,v2
q4	q4,v1	q2,v1	q1,v2

Еще один способ задания автомата – ориентированный мультиграф, называемый графом перехода или диаграммой переходов.

Вершины графа соответствуют состояниям; если (q_i,a_j)=q_k и (q_i,a_j)=V_e, то из q_i в q_k ведет ребро, на котором написаны a_j и V_e.

Кратные ребра не обязательны, например два ребра из q₂ в q₁ можно заменить одним ребром, на котором написаны обе пары q₃|V₁ и q₂|V₁.

Для любого графа переходов в каждой вершине q_i выполнены следующие условия, которые называются условиями автоматности и корректности:

1) для каждой входной буквы а_j имеется ребро, выходящее из q_i, на котором написанно a_j (условие полноты);

2) любая буква a_j встречается только на одном ребре, выходящим из q_i (условие непротиворечивости и детерминированности).

Для данного автомата S его функции _S и _S могут быть определены не только на множестве А всех входных букв, но и на множестве А^ всех входных слов. Для любого входного слова

,

Это традиционное определение с “многоточиями”. Немного точнее читается индуктивное определение:

1)  (q_i, a_j) задается автоматной таблицей S;

2 ) Для любого слова A* и любой буквы a_j

(q_i, a_j)= ( (q_i, ) ,a_j). (6.1)

С помощью расширенной функции  определятся расширенная функция 

(q_i, a_j)= ( (q_i, ) ,a_j). (6.2)

Зафиксируем в автомате S начальное состояние q₁ и каждому выходному слову поставим в соответствие слово  в выходном алфавите:

=(q_i, _aj1) (q_i, a_j1, a_j2)… (q_i, a_j1, a_j2 ,…,a_jk) (6.3)

Это соответствие, отображающее входные слова в выходные слова, называется автоматным отображением , а также автоматным (или ограниченно детерминированным) оператором, реализуемым оператором (S,q₁).

Иногда говорят кратко – оператор (S,q₁) или оператор S (если автомат S инициальный), и записывают S (q₁,)=  и S()=.

Число букв в  называют длиной слова  и обозначают || или l(). Автоматное отображение также удобно определить индуктивно:

(6.4)

Автоматное отображение обладает двумя свойствами, которые следуют из (6.3) и (6.4):

1. слова  и S()= имеют одну длину:||=||;

2. если =₁₂ и S(₁₂)=₁₂, где |₁|=|₁|, то S(₁)=₁. Другими словами: образ отрезка длиной i равен образу отрезка той же длины.

Свойство 2 отражает тот факт, что автоматные операторы – это операторы без предвосхищения, т.е. операторы, которые перерабатывая слово слева направо не «заглядывают вперед»: i-я буква выходного слова зависит только от i букв входного слова (пример оператора с предвосхищением – оператор отражения, ставящий в соответствие слову слово , здесь первая буква выходного слова равна последней входного).

Введенные определения (6.1)-(6.4) наглядно интерпретируются на графе переходов. Если зафиксированна вершина q_i, то всякое слово = однозначно определяет путь длины к из этой вершины (обозначим его (q_i, )), на к ребрах которого написаны соответственно буквы , поэтому (q_i, )- это последняя вершина пути (q_i, ); (q_i, )- выходная буква, написанная на последнем ребре пути (q_i, ), а отображение S(q_i, ) – слово, образованное к выходными буквами на к ребрах пути (q_i, ).

Пример 2: Для автомата S с заданной таблицей:

(q₂, a₃a₂)= (q₂, a₃a₁)=q₃,

(q₂, a₃a₁a₁)=q₂,

(q₂, a₃a₂)=v₂,

(q₂, a₃a₁)=v₁,

(q₂, a₃a₁ a₁)=v₁,

S(q₂, a₃a₂)= v₁v₂,

S(q₂, a₃a₁)=v₁ v₁,

S(q₂, a₃a₁ a₁)=v₁ v₁ v₁.

Состояние q_j называется достижимым из состояния q_i, если имеется входное слово , такое, что (q_i, )= q_j.

Автомат S называется сильно связным, если его входной алфавит состоит из одной буквы: А={a}, а все слова имеют вид ааа..а.

П ример 3:

Таблица 21

Q	a
1	3,0
2	4,0
3	4,0
4	7,0
5	4,2
6	5,0
7	6,1
8	9,0
9	9,1

Автоматная таблица и граф автономного автомата, задаваемый таблицей (входные буквы на ребрах опущены); выходной алфавит V={0,1,2}. Здесь и далее символы состояний q_i для краткости заменены их индексами.