СИСТЕМНЕ ПРОГРАМУВАННЯ ТА ОПЕРАЦІЙНІ СИСТЕМИ

1. Скінчені детерміновані автомати. Математична модель, форми представлення. Оптимізація.

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

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

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

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

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

Детермінований скінченний автомат 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. Якщо зустрілась парна кількість 0, M опиниться в стані S₁, допустимий стан, тож поданий на вхід рядок буде розпізнаний.

Мова розпізнавана M це регулярна мова задана регулярним виразом

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