- •Скінчені детерміновані автомати. Математична модель, форми представлення. Оптимізація.
- •Формальне визначення
- •Приклад
- •Переваги і недоліки
- •Стекові автомати. Представлення, операції, принцип роботи. Магазинний автомат (ма)
- •Стековий автомат (са)
- •Організація автомата з магазинною пам'яттю
- •Операції автомата
- •Регулярні вирази та граматики. Синтаксичні діаграми.
- •Синтаксис регулярних висловів
- •Модель мовного транслятора. Фази мовного аналізу.
- •Представлення синтаксичної структури формальної мови. Форма Бекуса-Наура.
- •Представлення проміжного коду. Елементарні операції, польський запис.
- •Формування проміжного коду
- •Поняття оптимізації проміжного коду. Оптимізаційні операції.
- •Графічне представлення лінійних ділянок проміжного коду. Перетворення на графах.
- •Загальна модель операційної системи. Загальна та машинно-залежна складові.
- •Забезпечення функцій ос. Управління пам’яттю та зовнішніми пристроями.
- •Підсистема управління оперативною пам'яттю
СИСТЕМНЕ ПРОГРАМУВАННЯ ТА ОПЕРАЦІЙНІ СИСТЕМИ
-
Скінчені детерміновані автомати. Математична модель, форми представлення. Оптимізація.
Приклад детермінованого скінченного автомата, який приймає тільки двійкові числа кратні 3. Стан S0 є одночасно початковим станом і допустимим станом.
В теорії алгоритмів і теорії автоматів, детермінований скінченний автомат (ДСА) — скінченний автомат, який приймає скінченний рядок символів. Для кожного стану існує стрілка переходу в наступний стан для кожного сиволу. По прочитанню символу, ДСА перестрибує детерміновано з одного стану в інший за відповідною стрілкою. Детермінованість означає наявність лише одного результату (тобто переходу в наступний стан для кожного символу (S0 -> Si) або повернення в той самий стан (S0 -> S0)). ДСА має початковий стан (позначений графічно стрілкою нізвідки) звідки починаються обчислення, і набір допустимих станів(позначених графічно двійними колами), які допомогають визначити успішність обчислень.
ДСА саме розпізнає набір регулярних мов, що є, між іншого, корисно для проведення лексичного аналізу і зіставляння із взірцем.[1] ДСА можна використати або в режимі приймача для перевірки належності вхідного рядка до мови, або в режимі генерації для створення списку всіх рядків в мові.
ДСА визначається як абстрактна математична концепція, яле через свою детермінованість, він може бути виконаним на апаратному або програмному рівні для розв'язання різних особливих задач. Наприклад, програмний автомат, який визначає є чи ні введений рядок вірним телефонним номером або електронною адресою. [2] Іншим прикладом на апаратному рівні є мікросхема, що керує автоматичними дверима, використовуючи вхідні дані від сенсорів руху або кнопок для визначення коли виконувати переходи між станами.
Формальне визначення
Детермінований скінченний автомат M це п'ятірка, (Q, Σ, δ, q0, F), де
-
скінченний набір станів станів (Q)
-
скінченний набір вхідних символів, абетка (Σ)
-
функція переходу (δ : Q × Σ → Q)
-
початковий стан (q0 ∈ Q)
-
набір допустимих станів (F ⊆ Q)
Нехай w = a1a2 ... an буде рядком над абеткою Σ. Автомат M приймає рядок w якщо послідовність станів, r0,r1, ..., rn в Q, відповідає наступним умовам:
-
r0 = q0
-
ri+1 = δ(ri, ai+1), for i = 0, ..., n−1
-
rn ∈ F.
Словами, перша умова каже, що починає з початкового стану q0. Друга умова каже, що з кожним наступним символом з w, автомат переходить зі стану в стан до функції переходу δ. Остання умова каже, що автомат приймає w якщо останній символ з w спричиняє перехід автомата в один з допустимих станів. Інакше, кажуть, що автоматвідхилив рядок. Набір допустимих рядків M це мова розпізнавана автоматом M і така мова позначається L(M).
Детермінований скінченний автомат без допустимих станів і без початкового стану відомий як модель станів і переходів або напівавтомат.
Приклад
Наступний приклад ДСА М, з двійковою абеткою, який розпізнає рядки з парною кількістю 0.
Діаграма станів для M
M = (Q, Σ, δ, q0, F) де
-
Q = {S1, S2},
-
Σ = {0, 1},
-
q0 = S1,
-
F = {S1}, і
-
δ визначена наступною таблицею переходів:
-
0
1
S1
S2
S1
S2
S1
S2
Стан S1 показує, що во вхідних даних, опрацьованих на даний час, зустрілась парна кількість 0, тоді як S2 вказує на непарну кількість. 1 на вході не змінює стану автомата. По завершені введення даних, стан буде вказувати чи зустрілась парна кількість 0. Якщо зустрілась парна кількість 0, M опиниться в стані S1, допустимий стан, тож поданий на вхід рядок буде розпізнаний.
Мова розпізнавана M це регулярна мова задана регулярним виразом
де "*" це зірка Кліні, тобто, 1* позначає будь-яку кількість (можливо нуль) символів "1".