✖

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

Kapitoly: Скінченний автомат, Повний автомат, Недетермінований скінченний автомат, Симуляція недетермінованого автомата, Перетворення НСА на ДСА

Скінченний автомат (англійською finite state machine або finite automaton) — це обчислювальна модель примітивного комп'ютера, що складається з кількох станів і кількох переходів і може допустити або відхилити подане слово.

Приклад

Неформально опишемо скінченний автомат за допомогою діаграми станів, яка зображує скінченний автомат:

Приклад простого скінченного автомата

Автомат складається зі станів; на рисунку це три круглі стани q0, q1 і q2. Між цими станами є переходи — це стрілки. В автоматі також має бути початковий стан, тут це стан q0. Початковий стан часто зображують так, що в нього спрямована стрілка, яка не виходить з жодного стану. Далі в автоматі зазвичай є заключний стан; його зображують подвійною лінією, тож на рисунку це стан q2.

Автомат, побудований таким чином, допускає певні слова. Ми подаємо в автомат якісь слова, і він намагається їх допустити. Якщо допускає, автомат відповідає ТАК, якщо ні — НІ. Наш автомат намагається допускати слова, що складаються з літер «a, b, c», тож можемо спробувати допустити слово «abbc».

Починаємо в початковому стані q0, на вході слово «abbc». Далі йдемо за стрілками.

Слово проходимо звично зліва направо, тобто першим візьмемо символ «a». Стрілка для входу «a» веде в стан q1, тож переходимо туди й вилучаємо символ «a» зі слова. На вході залишилося слово «bbc»:

Стрілка для входу «b» веде назад у вузол q1. Знову вилучаємо першу літеру, і на вході залишається слово «bc». Знову залишаємося в стані q1. Нарешті на вході залишилося слово «c». Зі стану q1 стрілка для входу «c» відправляє нас у стан q2.

Ми вичерпали всі літери вхідного слова й перебуваємо в стані q2, який є заключним. Отже, цей скінченний автомат допускає слово «abbc».

Якби наприкінці ми були не в заключному стані, автомат слова б не допустив. Так само автомат не допустив би слово, якби в якомусь стані нам не було куди йти. Наприклад, для входу «ab» ми потрапили б у стан q1 і там би й завершили — автомат таке слово не допускає. Якщо ж перевірити слово «aabbc», то нам знову не пощастить, бо зі стану q1 не веде стрілка для літери «a».

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

Означення скінченного автомата

Попереднє інтуїтивне уявлення про скінченний автомат треба формалізувати, щоб ми могли з автоматами далі краще працювати.

Скажемо, що скінченний (детермінований) автомат — це п'ятірка $\left<Q, \Sigma, \delta, q_0, F\right>$, де

  • Q — скінченна множина станів,
  • $\Sigma$ (велика сигма) — алфавіт (скінченна множина символів/літер),
  • $\delta: Q \times \Sigma\longrightarrow Q$ — функція переходів,
  • q0 ∈ Q — початковий стан,
  • F ⊆ Q — множина заключних (фінальних) станів.

Повернімося до попереднього автомата,

і скажімо, що в множині станів Q є три стани Q = {q0, q1, q2}. Алфавіт $\Sigma$ містить літери, з яких можна складати слова, що їх автомат допускатиме або відхилятиме. Тут це, імовірно, алфавіт $\Sigma=\left\{a, b, c\right\}$, але може бути й довільна надмножина. Початковий стан q0 — це стан q0, тут нічого не змінюється. Множина заключних станів у цьому автоматі має лише один стан F = {q2}.

Функцією переходів тоді називаємо ті три стрілки з літерами. Якщо тебе плутає запис $\delta: Q \times \Sigma\longrightarrow Q$, то він означає лише, що δ — це функція (точніше, відображення), яка бере два аргументи: стан із Q і літеру з $\Sigma$. Після виклику функція повертає новий стан. Нашу функцію переходів можна було б задати таблицею так:

$$ \begin{array}{cc|c} Q&\Sigma&\rightarrow Q\\\hline q_0&a&q_1\\ q_1&b&q_1\\ q_1&c&q_2\\ \end{array} $$

Якщо викликати δ(q1, c), застосовуємо третій рядок, і функція відповідає станом q2 — так само, як діаграма. Якщо ми в стані q1 і на вході літера «c», то потрапляємо в стан q2. Перш ніж формально означити, що саме означає «автомат допускає слово», скористаємося інтуїтивним розумінням цього поняття й розглянемо ще кілька прикладів.

Інші приклади

  1. Побудуй автомат, який працює над двійковим алфавітом, тобто $\Sigma=\left\{0,1\right\}$, і допускає лише слова, що закінчуються одиницею. Наприклад, допускає слова 1, 01, 000001, 0101011.

    Наш автомат має два стани — початковий q0 і заключний q1. Щоразу, коли на вході цифра 1, переходимо в заключний стан q1 і залишаємося в ньому. Натомість якщо на вході цифра 0, переходимо в незаключний стан q0 і також залишаємося в ньому.

  2. Побудуй автомат над двійковим алфавітом, який допускає лише слова, перша літера яких відмінна від останньої.

    Уже на першому кроці автомат розгалужується на два «підавтомати». Якщо слово починається з нуля, автомат заходить у ліву частину й там залишається, якщо починається з одиниці — переходить у праву частину. Далі все стандартно: якщо ми в лівій частині й на вході 1, переходимо в заключний стан і залишаємося в ньому. Якщо на вході 0, переходимо в стан q1, який не є заключним.

    На відміну від попередніх автоматів, цей автомат має кілька заключних станів, тобто F = {q3, q4}.

  3. Побудуй автомат над двійковим алфавітом, який допускає лише слова, що не містять двох нулів підряд.

    Цей автомат цікавий з двох причин: по-перше, він допускає порожнє слово. Ми можемо спробувати подати в автомат порожнє слово, і він його допустить, якщо початковий стан водночас є заключним, що в цьому автоматі й сталося. Оскільки порожнє слово не містить двох нулів підряд, це правильно. Інша цікава властивість — усі стани цього автомата заключні. Єдиний випадок, коли автомат не допустить слово, — це коли зі стану не веде жодного переходу. Так стається в стані q1, який не має переходу для 0, адже тоді слово містило б два нулі підряд.

  4. Побудуй автомат над алфавітом {-,+,.,0,1,…,9}, який допускає лише слова, що зображують число. Тобто або ціле число, наприклад 2, 548, 98263, або десятковий дріб, наприклад 5584.48, 3.14 (у словах для автомата, як і на рисунку, використовуємо крапку), причому і те, і те ще й у версії для від'ємного числа зі знаком мінус -2, -548, -3.14, а також із явно вказаним плюсом, тобто +2, +548, +3.14. Водночас ми повинні мати змогу записати число 0.123 просто як .123 (без нуля на початку), і то з обома знаками. Введемо допоміжне позначення: замість того щоб виписувати десять переходів для десяти цифр, використаємо символ N.

  5. Побудуй автомат над двійковим алфавітом, який допускає лише слова вигляду 0n1n, тобто слова мають на початку певну кількість нулів, а за ними йде така сама кількість одиниць. Приклади таких слів — 0011, 00001111, 01.

    Такий автомат побудувати неможливо, бо ми ніде не можемо «запам'ятати» кількість нулів. Довелося б створити кілька «підавтоматів», подібно до другого прикладу, але таких «підавтоматів» мало б бути нескінченно багато — по одному для кожного значення n.

Формалізація обчислення автомата

Ми вже формально означили сам скінченний автомат. Далі треба ще означити, що такий автомат, власне, робить, тобто означити обчислення автомата.

Конфігурація автомата: скажемо, що пара $\left<q, w\right> \in Q \times \Sigma^\ast$ є конфігурацією автомата, де q — поточний стан, у якому перебуває автомат, а w — іще не прочитана частина слова. $\Sigma^\ast$ позначає замикання алфавіту $\Sigma$, множину всіх слів, які можна скласти з літер алфавіту $\Sigma$. До замикання належить і порожнє слово, яке позначаємо $\varepsilon$.

Якщо маємо автомат $\left<Q, \Sigma, \delta, q_0, F\right>$ і намагаємося допустити слово w, то автомат перебуває в початковій конфігурації <q0, w>. Якщо повернутися до автомата

і захотіти допустити слово w = abbc, то початкова конфігурація буде <q0, abbc>.

Крок обчислення означаємо як відношення $\mapsto$ між множинами $(Q\times\Sigma^\ast)\times(Q\times\Sigma^\ast)$, тобто між конфігураціями автомата. Нехай w = w0w1… wn — іще не прочитана частина слова w. Тоді скажемо, що пари <q1, w0w1… wn> і <q2, w1… wn> перебувають у відношенні $\mapsto$, і запишемо це як

$$ \left<q_1, w_0w_1\dots w_n\right> \mapsto \left<q_2, w_1\dots w_n\right>, $$

тоді й лише тоді, коли δ(q1, w0) = q2. Повертаючись до нашого прикладу, початкова конфігурація — <q0, abbc>. З діаграми бачимо, що для входу «a» можемо перейти в стан q1. Тож можемо записати

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right>, $$

бо виконується δ(q0, a) = q1. Так ми виконали один крок обчислення — подивилися, в який стан треба перейти для даного входу (= першої літери іще не прочитаної частини слова), перейшли туди й вилучили з не прочитаної частини слова першу літеру. Так ми отримали нову конфігурацію.

Рефлексивне й транзитивне замикання відношення «крок обчислення» позначаємо $\mapsto^\ast$. Якщо ми запишемо $K_1 \mapsto^\ast K_2$, де K1, K2 — конфігурації автомата, то це означає, що з конфігурації K1 за кілька кроків обчислення можна дійти до конфігурації K2, тобто існує скінченна послідовність конфігурацій така, що:

$$ K_1 \mapsto K_{11} \mapsto K_{12} \mapsto K_{13} \mapsto \dots \mapsto K_2 $$

Наприклад, у нашому автоматі виконується $\left<q_0, abbc\right> \mapsto^\ast \left<q_1,bc\right>$, бо після двох кроків обчислення залишиться слово «bc», а ми будемо в стані q1. Тобто існує така послідовність конфігурацій:

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right> \mapsto \left<q_1,bc\right> $$

Автомат допускає слово w тоді й лише тоді, коли існує qf ∈ F таке, що $$\left<q_0, w\right> \mapsto^\ast \left<q_f, \varepsilon\right>$$ Це означає, що автомат допускає слово w тоді й лише тоді, коли існує така послідовність кроків обчислення, що наприкінці цієї послідовності ми прочитали все слово й перебуваємо в заключному стані автомата. Те, що ми прочитали все слово, виражено тим, що в конфігурації на місці слова стоїть $\varepsilon$ — порожнє слово. Наш автомат допускає слово abbc, бо існує така послідовність конфігурацій:

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right> \mapsto \left<q_1,bc\right> \mapsto \left<q_1, c\right> \mapsto \left<q_2, \varepsilon\right> $$

а стан q2 є заключним, q2 ∈ F.

Мова, яку допускає автомат, — це множина всіх слів, які автомат допускає. Мову автомата A позначатимемо L(A). Отже, $L(A) \subseteq \Sigma^\ast$ і

$$ L(A) = \left\{w \in \Sigma^\ast,|,A \mbox{ допускає слово } w\right\} $$

Регулярна мова — це мова, яку розпізнає деякий скінченний автомат.

Два скінченні автомати еквівалентні, якщо вони допускають однакову мову. Тобто автомати A1 і A2 еквівалентні, якщо виконується L(A1) = L(A2).

Джерела