3.5. Основные понятия теории конечных автоматов

Конечным автоматом называется система S={A, Q ,V, }, в которой A={a₁,…,a_m}, Q={q₁,…q_n}, V={v₁,…,v_k} - конечные множества (алфавиты); a  : Q x A  Q и  : Q x A  V - функции, определенные на этих множествах. А называется входным алфавитом, V - выходным алфавитом, Q - алфавитом состояния;  – функцией переходов,  – функцией выходов. Если, кроме того, в автомате S выделено одно состояние, называемое начальным (будем считать, что это состояние q₀), то полученный автомат называется инициальным и обозначается ( S ,q₀ ) ; таким образом, по не инициальному автомату с n состояниями можно n различными способами определить инициальный автомат.

Поскольку функции  и определены на конечных множествах, их можно задавать таблицами. Обычно две таблицы сводятся в одну таблицу  и , называемую таблицей переходов - выходов автомата или автоматной таблицей.

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

Таблица 3.5 - Табличное задание конечного автомата

	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_l, то из q_i в q_k ведет ребро, на котором написаны a_j и v_l . Граф переходов для таблицы 3.5 изображен на рис. 3.7. Кратные ребра не обязательны; например два ребра из q₂ в q₁ можно заменить одним, на котором будут написаны обе пары a₃/v₁ и a₂/v₁ . Для любого графа переходов в каждой вершине q_i выполнены следующие условия, которые называются условиями корректности:

1) Для любой входной буквы ai имеется ребро, выходящее из qi , на котором написано aj (условие полноты);

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

Для данного автомата S его функции _S и _S могут быть определены не только на множестве А всех выходных букв, но и на множестве А* всех входных слов. Для любого входного слова _j _j2_jkq_i, a_j1, a_j2,…, a_jk q_i, a_j1), a_j2) ,…, a_jk-₁), a_jk).

a₁/v₁

a₁/v₁

a₂/v₁

a₁/v₁

a₂/v₁

a₃/v₁

a₃/v₂

a₂/v₂

a₁/v₁

a₁/v₁

a₂/v₁

a₃/v₂

Рис.3.7 - Граф конечного автомата

Другим способом это традиционное определение можно представить следующим образом:

1. 1)  ( Qi , aj ) задается автоматной таблицей s;

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

q_i,a_jq_i,a_j).

Здесь и в дальнейшем символы состояний для кратности обозначений будут заменяться их индексами.

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

q_ia_jq_ja_j).

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

q₁, a_j1q₁,a_j1a_j2q₁,a_j1,…,a_jk.

Это соответствие, отображающее входные слова в выходные слова называется автоматным отображением, а так же автоматным оператором. Если результатом применения оператора к слову  является выходное слово , то это будем обозначать соответственно S (q₁, )=  или S( )= . Число букв в слове , как обычно является длиной  и обозначается или l(.

Автоматное отображение обладает следующими свойствами:

• слова  и  = S( ) имеют одинаковую длину;

• если  = __ и S(__)= __ , где _= _ , то S( _ )= _ ;

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

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