Скінчені автомати

Означення: Недетермінований скінчений автомат – це п’ятірка

М = < Q, S, d, q₀, F>, де

Q = {q₀, q₁,.., q_n-1} – скінчена множина станів автомата;

S = {a₁, a₂,.., a_m} – скінчена множина вхідних символів (вхідний алфавіт);

q₀ Î Q – початковий стан автомата;

d – відображення множини Q*S в множину P (Q). Відображення d як правило називають функцією переходів;

F Í Q – множина заключних станів. Елементи з F називають заключними або фінальними станами.

Якщо М – скінчений автомат, то пара (q, w) Î Q_*S* називається конфігурацією автомата М. Оскільки скінчений автомат – це дискретний пристрій, він працює по тактам. Такт скінченого автомата М задається бінарним відношенням |=, яке визначається на конфігураціях:

(q₁,aw) |= (q₂,w), якщо d(q₁, a) містить q₂ та для всіх w Î S*.

Означення. Скінчений автомат М розпізнає (допускає) ланцюжок w, якщо

(q₀, w) |=* (q, e) для деякого q Î F, де

|=* - рефлексивно-транзитивне замикання бінарного відношення |=.

Означення. Мова, яку допускає автомат М (розпізнає автомат М)

L(M)={ w | w Î S* та (q₀, w) |=* (q, e), q Î F }

На практиці, при визначенні скінченого автомата М, використовують декілька способів визначення функції d, наприклад:

це табличне визначення d;

діаграма проходів скінченого автомата.

Табличне визначення функції d - це таблиця М(q_i,a_j), де a_j Î S, q_i Î Q, тобто

М(q_i,a_j) = { q_k |, q_k Î d(q_i,a_j ) }

Діаграма переходів скінченого автомата М - це невпорядкований граф G(V, P), де V – множина вершин графа, а P – множина орієнтованих дуг, причому з вершини q_i у вершину q_j веде дуга позначена a_k , коли q_jÎd(q_i,a_k ). На діаграмі переходів скінченого автомата це позначається так:

a_k

q_i q_j

В подальшому, на діаграмі переходів скінченого автомата М елементи з множини заключних станів будемо позначити так: q_i.

Приклад 1. Побудуємо діаграму переходів скінченого автомата М, який розпізнає множину цілочислових констант мови С.

U, u

1,.., 9 L, l

1,.., 9 U, u L,l

q₀ 0,.., 7

L, l U, u

0 0,.., 7

U, u L, l

A,.., F,a,.., f, 0,.., 9

X, x

A,.. F, U, u L, l

a,.., f, L, l

0,.., 9 U, u

Мал. 1.

З побудованого прикладу видно, що приведений автомат не повністю визначений.

Означення. Скінчений автомат М називається детермінованим, якщо d(q_i, a_k) містить не більше одного стану для любого q_i Î Q та a_k Î S.

Твердження: Для довільного недетермінованого скінченого автомата М можна побудувати еквівалентний йому детермінований скінчений автомат М₁, такий що

L(M) = L(M₁).

Доведення: Нехай М – недетермінований скінчений автомат, такий що

М=< Q, S, d, q₀, F>

Детермінований автомат М₁=< Q₁, S, d₁, q₀₁, F₁> побудуємо таким чином:

- Q₁ = P (Q), тобто імена станів автомата М1 – це підмножини множини Q.

- q₀₁= { q₀ }, { q₀ } Î P (Q).

- F₁ складається з усіх таких підмножин S Î P (Q), таких що S Ç А ¹ Æ.

- d₁(S, a) = {q | q Î d(q_i, a), q_i Î S }.

Доведемо індукцією по i, що (S,w) |=ⁱ (S₁,e), тоді і тільки тоді, коли

S₁= { q | (q_i, w)) |=ⁱ (q, e), для q_i Î S },

Зокрема, ({q₀}, w) |=* (S₁, e), для деякого S₁ Î F₁, тоді і тільки тоді, коли

(q₀, w) |=* (q, e), q Î F. Таким чином, L(M) = L(M₁).

Побудований нами автомат М має дві властивості: він детермінований та повністю визначений. До того ж кількість станів цього автомата 2ⁿ – 1.