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