Детермінований скінченний автомат: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування Мітки: Візуальний редактор Редагування з мобільного пристрою Редагування через мобільну версію |
Немає опису редагування |
||
Рядок 3:
В [[теорія алгоритмів|теорії алгоритмів]] і [[теорія автоматів|теорії автоматів]], '''детермінований скінченний автомат''' ('''ДСА''') — [[скінченний автомат]], який приймає скінченний рядок символів. Для кожного стану існує стрілка переходу в наступний стан для кожного символу. Після зчитування символу ДСА перестрибує ''детерміновано'' з одного стану в інший за відповідною стрілкою. [[Детермінованість]] означає наявність лише одного результату (тобто переходу в наступний стан для кожного символу (S0 -> Si) або повернення в той самий стан (S0 -> S0)). ДСА має [[Скінченний автомат#Початковий стан|початковий стан]] (позначений графічно стрілкою нізвідки), звідки починаються обчислення, і [[Множина|набір]] [[Скінченний автомат#Допустимі стани|допустимих станів]] (позначених графічно двійними колами), які допомагають визначити успішність обчислень.
ДСА саме розпізнає набір [[регулярна мова|регулярних мов]], що є, між іншим, корисним для проведення [[лексичний аналіз|лексичного аналізу]] і
<ref>{{Cite web
|last = Fegaras
| |||