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

Детермінований скінченний автомат 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₁}, і
• δ визначена такою таблицею переходів:

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

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

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

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

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

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

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

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

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

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