Детермінований скінченний автомат

В теорії алгоритмів і теорії автоматів, детермінований скінченний автомат (ДСА) — скінченний автомат, який приймає скінченний рядок символів. Для кожного стану існує стрілка переходу в наступний стан для кожного символу. Після зчитування символу ДСА перестрибує детерміновано з одного стану в інший за відповідною стрілкою. Детермінованість означає наявність лише одного результату (тобто переходу в наступний стан для кожного символу (S0 -> Si) або повернення в той самий стан (S0 -> S0)). ДСА має початковий стан (позначений графічно стрілкою нізвідки), звідки починаються обчислення, і набір допустимих станів (позначених графічно двійними колами), які допомагають визначити успішність обчислень.

Приклад детермінованого скінченного автомата, який приймає тільки двійкові числа кратні 3. Стан S₀ є одночасно початковим станом і допустимим станом.

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

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

Формальне визначення

Детермінований скінченний автомат M це п'ятірка, (Q, Σ, δ, q₀, F), де

• скінченний набір станів станів (Q)
• скінченний набір вхідних символів, абетка (Σ)
• функція переходу (δ : Q × Σ → Q)
• початковий стан (q₀ ∈ Q)
• набір допустимих станів (F ⊆ Q)

Нехай w = a₁a₂ … a_n - рядок над абеткою Σ. Автомат M приймає рядок w, якщо послідовність станів, r₀,r₁, …, r_n в Q, відповідає таким умовам:

1. r₀ = q₀
2. r_i+1 = δ(r_i, a_i+1), for i = 0, …, n−1
3. r_n ∈ F.

Словами, перша умова каже, що автомат починає з початкового стану q₀. Друга умова каже, що з кожним наступним символом з w автомат переходить зі стану в стан до функції переходу δ. Остання умова каже, що автомат приймає w, якщо останній символ з w спричиняє перехід автомата в один з допустимих станів. Інакше, кажуть, що автомат відхилив рядок. Набір допустимих рядків M - це мова , що розпізнається автоматом M, і така мова позначається L(M).

Детермінований скінченний автомат без допустимих станів і без початкового стану відомий як модель станів і переходів або напівавтомат.

Приклад

Нижче наведено приклад ДСА М з двійковою абеткою, який розпізнає рядки з парною кількістю 0.

Діаграма станів для M

M = (Q, Σ, δ, q₀, F), де

• Q = {S₁, S₂},
• Σ = {0, 1},
• q₀ = S₁,
• F = {S₁}, і
• δ визначена такою таблицею переходів:

	0	1
S1	S2	S1
S2	S1	S2

Стан S₁ показує, що серед вхідних даних, наразі опрацьованих , трапилася парна кількість 0, тоді як S₂ вказує на непарну кількість. 1 на вході не змінює стану автомата. Після завершення введення даних стан буде вказувати, чи трапилась парна кількість 0. Якщо так дійсно сталося, M опиниться в стані S₁, що є допустимим станом, тож поданий на вхід рядок буде розпізнаний.

Мова, що розпізнається M, - це регулярна мова, задана регулярним виразом

$1^{*}{\bigl (}0(1^{*})0(1^{*}){\bigr )}^{*},\,$

де «*» - це зірка Кліні, тобто 1* позначає будь-яку кількість (можливо нуль) символів «1».

Еквівалентні моделі

Незмінна машина Тюринга з рухом праворуч

Незмінні машини Тюринга з рухом праворуч це різновид машин Тюринга яка рухається лише вправо. Вони майже цілком еквівалентні ДСкА.

Визначається як кортеж з 7 елементів:

$M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle ,$

де

$Q$ скінченна множина станів;

$\Gamma$ скінченна множина символів стрічки;

$b\in \Gamma$ - порожній символ (єдиний символ який зустрічається на стрічці нескінченну кількість разів);

$\Sigma$, підмножина $\Gamma$ що не включає b, множина вхідних символів;

$\delta :Q\times \Gamma \to Q\times \Gamma \times \{R\}$ це функція яка називається фукнцією переходів, R це рух вправо;

$q_{0}\in Q$ - початковий стан;

$F\subseteq Q$ множина фінальних або допустимих станів.

Така машина завжди приймає регулярну мову. Повинен існувати хоча б один елемент множини F (стан HALT) для того аби мова була не порожньою.

Приклад незмінної машиши Тюринга з 3 станами і 2 символами

	В стані A			В стані B			В стані C
символ на стрічці	Записати символ	Переміщення	Наступний стан	Записати символ	Переміщення	Наступний стан	Записати символ	Переміщення	Наступний стан
0	1	R	B	1	R	A	1	R	B
1	1	R	C	1	R	B	1	N	HALT

$Q=\{A,B,C,{\text{HALT}}\};$

$\Gamma =\{0,1\};$

$b=0$, "порожній";

$\Sigma =\varnothing$, порожня множина;

$\delta =$ див таблицю станів вище;

$q_{0}=A$, початковий стан;

$F=$ одноелемента множина кінцевих станів: $\{{\text{HALT}}\}$.

Переваги і недоліки

ДСА — одна з найпрактичніших моделей обчислення через свій лінійний час, сталу потребу в пам'яті, можливість обробки за допомогою послідовного алгоритму. Для даних двох ДСА існують дієві алгоритми для знаходження ДСА, що розпізнає:

• об'єднання двох ДСА;
• перетин двох ДСА;
• комплементарну мову до розпізнаваної ДСА.

Завдяки можливості зведення ДСА до канонічної форми (найменшого ДСА), існують дієві алгоритми для визначення:

• чи приймає ДСА будь-який рядок;
• чи приймає ДСА всі рядки;
• чи розпізнають два ДСА ту саму мову;
• ДСА з найменшою кількістю станів для окремої мови.

ДСА тотожний за силою обчислення до недетермінованого скінченного автомата.

З іншого боку, ДСА сильно обмежений в мовах, які він може розпізнати; багато простих мов з урахуванням будь-якої задачі, яка вимагає непостійного місця в пам'яті для розв'язання, не можуть бути розпізнані за допомогою ДСА. Класичний приклад просто описаної мови, яку не може розпізнати ДСА, - це мова дужок мови, що містить правильні дужкові послідовності, такі як (()()). Більш формально, мову утворену рядками типу aⁿbⁿ—деяка скінченна кількість a, услід за рівною кількістю b. Якщо немає обмеження на рекурсію (тобто ви можете завжди вставити іншу пару дужок усередину), то буде потрібна нескінченна кількість станів для розпізнавання.

Див. також

• Недетермінований скінченний автомат

Література

• Гаврилків В. М. Формальні мови та алгоритмічні моделі. — І.-Ф.  : Голіней, 2023. — 180 с.