Перегляд вихідного коду сторінки Детермінований скінченний автомат

[[Файл:DFA example multiplies of 3.svg|thumb|250px |right|Приклад детермінованого скінченного автомата, який приймає тільки двійкові числа кратні 3. Стан S<sub>0</sub> є одночасно початковим станом і допустимим станом.]]

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

ДСА саме розпізнає набір [[регулярна мова|регулярних мов]], що є, між іншим, корисним для проведення [[лексичний аналіз|лексичного аналізу]] і [[зіставляння зі взірцем]].
<ref>{{Cite web
 |last        = Fegaras
 |first       = Leonidas
 |title       = Converting a Regular Expression into a Deterministic Finite Automaton
 |url         = http://lambda.uta.edu/cse5317/notes/node9.html
 |accessdate  = 2011-02-17
 |archiveurl  = https://web.archive.org/web/20110519000234/http://lambda.uta.edu/cse5317/notes/node9.html
 |archivedate = 2011-05-19
 |deadurl     = yes
}}</ref>
ДСА можна використати або в режимі приймача для перевірки належності вхідного рядка до мови, або в режимі генерації для створення списку всіх рядків у мові.

ДСА визначається як абстрактна математична концепція, але через свою детермінованість він може бути виконаним на апаратному або програмному рівні для розв'язання різних особливих задач. Наприклад, програмний автомат, який визначає чи є введений рядок правильним телефонним номером або електронною адресою.
<ref>{{Citation
  | last = Gouda
  | first = Prabhakar
  | title = Application of Finite automata
  | accessdate = 4 August 2010 }}</ref>
Іншим прикладом на апаратному рівні є [[мікросхема]], що керує автоматичними дверима, використовуючи вхідні дані від сенсорів руху або кнопок для визначення моменту, коли треба виконувати переходи між станами.

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

'''Детермінований скінченний автомат''' ''M'' це [[кортеж|п'ятірка]],
(''Q'', Σ, δ, ''q''<sub>''0''</sub>, ''F''), де
* скінченний набір станів [[Стан (інформатика)|станів]] (''Q'')
* скінченний набір вхідних символів, [[Абетка (інформатика)|абетка]] (Σ)
* [[функція (математика)|функція]] переходу (δ : ''Q'' &times; Σ → ''Q'')
* [[Скінченний автомат#Початковий стан|початковий стан]] (''q''<sub>''0''</sub> ∈ ''Q'')
* набір [[Скінченний автомат#Допустимі стани|допустимих станів]] (''F'' ⊆ ''Q'')

Нехай ''w = a<sub>1</sub>a<sub>2</sub> … a<sub>n</sub>'' - рядок над абеткою Σ. Автомат ''M'' приймає рядок ''w,'' якщо послідовність станів,
''r<sub>0</sub>,r<sub>1</sub>, …, r<sub>n</sub>'' в ''Q'', відповідає таким умовам:
# ''r<sub>0</sub>'' = ''q''<sub>''0''</sub>
# ''r<sub>i+1</sub>'' = δ(''r<sub>i</sub>'', ''a<sub>i+1</sub>''), for ''i'' = ''0, …, n−1''
# ''r<sub>n</sub>'' ∈ ''F''.

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

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

== Приклад ==

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

[[Файл:DFAexample.svg|right|thumb|250px|[[Діаграма станів]] для ''M'']]
''M'' = (''Q'', Σ, δ, ''q<sub>0</sub>'', ''F''), де
* ''Q'' = {''S''<sub>1</sub>, ''S''<sub>2</sub>},
* Σ = {0, 1},
* ''q<sub>0</sub>'' = ''S''<sub>1</sub>,
* ''F'' = {''S''<sub>1</sub>}, і
* δ визначена такою таблицею переходів:
{| border="1" cellpadding="1" cellspacing="0"
| || <center>'''0'''</center> || <center>'''1'''</center>
|-
|'''''S''<sub>1</sub>''' || ''S''<sub>2</sub> || ''S''<sub>1</sub>
|-
|'''''S''<sub>2</sub>''' || ''S''<sub>1</sub> || ''S''<sub>2</sub>
|}

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

Мова, що розпізнається ''M, -'' це [[регулярна мова]], задана [[регулярний вираз|регулярним виразом]]
: <math> 1^* \bigl( 0 (1^*) 0 (1^*) \bigr)^*, \,</math>

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

== Еквівалентні моделі ==
=== Незмінна машина Тюринга з рухом праворуч ===
{{Тюрінг}}
'''Незмінні машини Тюринга з рухом праворуч''' це різновид [[Машина Тюринга|машин Тюринга]] яка рухається лише вправо. Вони майже цілком еквівалентні ДСкА.<ref name=RORMTM>{{cite book | last = Davis| first = Martin |author2=Ron Sigal |author3=Elaine J. Weyuker | title = Second Edition: Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science | edition = 2nd | publisher = Academic Press, Harcourt, Brace & Company| location = San Diego | year = 1994| ISBN =0-12-206382-1}}</ref>

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

: <math>M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle,</math>
де
: <math>Q</math> скінченна множина ''станів'';
: <math>\Gamma</math> скінченна множина ''символів стрічки'';
: <math>b \in \Gamma</math> - ''порожній символ'' (єдиний символ який зустрічається на стрічці нескінченну кількість разів);
: <math>\Sigma</math>, підмножина <math>\Gamma</math> що не включає ''b'', множина ''вхідних символів'';
: <math>\delta: Q \times \Gamma \to Q \times \Gamma \times \{R\}</math> це [[функція (математика)|функція]] яка називається ''[[Модель станів і переходів|функцією переходів]]'', ''R'' це рух вправо;
: <math>q_0 \in Q</math> - ''початковий стан'';
: <math>F \subseteq Q</math> множина ''фінальних'' або ''допустимих станів''.

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

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

{|class="wikitable"
|-
|
| colspan="3" | В стані '''A'''
| colspan="3" | В стані '''B'''
| colspan="3" | В стані '''C'''
|-
! символ на стрічці 
! Записати символ
! Переміщення
! Наступний стан
! Записати символ
! Переміщення
! Наступний стан
! Записати символ
! Переміщення
! Наступний стан
|-
! 0
 | 1
 | R
|style="font-weight:bold" | B
 | 1
 | R
|style="font-weight:bold" | A
 | 1
 | R
|style="font-weight:bold" | B
|-
! 1
 | 1
 | R
|style="font-weight:bold" | C
 | 1
 | R
|style="font-weight:bold" | B
 | 1
 | N
 | '''HALT'''
|}

: <math>Q = \{ A, B, C, \text{HALT} \};</math>
: <math>\Gamma = \{ 0, 1 \};</math>
: <math>b = 0</math>, "порожній";
: <math>\Sigma = \varnothing</math>, [[порожня множина]];
: <math>\delta = </math> див таблицю станів вище;
: <math>q_0 = A</math>, початковий стан;
: <math>F = </math> одноелемента множина кінцевих станів: <math>\{\text{HALT}\}</math>.

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

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

Завдяки можливості зведення ДСА до ''канонічної форми'' ([[ДСА мінімізація|найменшого ДСА]]), існують дієві алгоритми для визначення:
* чи приймає ДСА будь-який рядок;
* чи приймає ДСА всі рядки;
* чи розпізнають два ДСА ту саму мову;
* ДСА з найменшою кількістю станів для окремої мови.

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

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

== Див. також ==
* [[Недетермінований скінченний автомат]]

== Примітки ==
{{reflist}}

== Література ==
* {{книга
|автор        = [[Гаврилків Володимир Михайлович|Гаврилків В. М.]]
|назва        = Формальні мови та алгоритмічні моделі
|рік          = 2023
|видавництво  = Голіней
|місто        = {{Comment|І.-Ф. |Івано-Франківськ}}
|сторінок     = 180
|мова         = uk
}}
* {{Cinderella Book}}
* {{Роджерс.Теорія рекурсивних функцій}}

[[Категорія:Теорія автоматів]]
[[Категорія:Скінченні автомати]]