3.6. Основні поняття теорії скінченних автоматів

Скінченним автоматом називається система 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) для будь-якої вхідної букви a_i є ребро, що виходить із q_i, на якому написане a_j (умовна повнота);

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

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

 q_i, a_j1), a_j2), … , a_jk-₁), a_jk).

Іншим способом це традиційне визначення можна представити так:

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

2) для будь-якого слова А* і будь-якої букви а_j

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

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

Тут і надалі символи станів для формування коротких позначень будуть замінятися їхніми індексами.

За допомогою розширеної функції  визначається (індуктивно) розширена функція .

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

Зафіксуємо в автоматі S початковий стан q_1, і кожному вхідному слову  = а_j1, а_j2, …, а_jk поставимо у відповідність слово  у вихідному алфавіті

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

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

Автоматне відображення має такі властивості:

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

• якщо  = __ і S(__)= __ , де _= _ , то S( _ )= _.

Остання властивість відбиває той факт, що автоматні оператори - це оператори, які, переробляючи слово зліва праворуч, не «заглядають вперед». При цьому i - а буква вихідного слова залежить тільки від перших i - букв вихідного слова.

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