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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Приклад детермінованого скінченного автомата, який приймає тільки двійкові числа кратні 3. Стан S0 є одночасно початковим станом і допустимим станом.

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

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

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

Формальне визначення[ред.ред. код]

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

Нехай w = a1a2 ... an буде рядком над абеткою Σ. Автомат M приймає рядок w якщо послідовність станів, r0,r1, ..., rn в Q, відповідає наступним умовам:

  1. r0 = q0
  2. ri+1 = δ(ri, ai+1), for i = 0, ..., n−1
  3. rnF.

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

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

Приклад[ред.ред. код]

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

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^* \bigl( 0 (1^*) 0 (1^*) \bigr)^*, \,

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

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

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

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

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

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

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

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

Примітки[ред.ред. код]

  1. Fegaras, Leonidas. «Converting a Regular Expression into a Deterministic Finite Automaton». Архів оригіналу за 2013-07-16. Процитовано 2011-02-17. 
  2. Gouda, Prabhakar, Application of Finite automata