Недетерминированный конечный автомат
вид конечного автомата / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Недетерминированный конечный автомат?
Кратко изложите эту статью для 10-летнего ребёнка
Недетерминированный конечный автомат (НКА, англ. nondeterministic finite automaton, NFA) — это детерминированный конечный автомат (ДКА, англ. deterministic finite automaton, DFA), который не выполняет следующие условия:
- любой его переход единственным образом определяется по текущему состоянию и входному символу
- чтение входного символа требуется для каждого изменения состояния.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/5/59/Relatively_small_NFA.svg/100px-Relatively_small_NFA.svg.png)
Для этого языка у ДКА будет по меньшей мере 16 состояний
В частности, любой ДКА является также НКА.
Используя алгоритм конструкции подмножеств[англ.], любой НКА можно преобразовать в эквивалентный ДКА, то есть ДКА, распознающий тот же самый формальный язык[1]. Подобно ДКА, НКА распознаёт только регулярные языки.
НКА предложили в 1959 году Михаэль О. Рабин и Дана Скотт[2], которые показали его эквивалентность ДКА. НКА используется в реализации регулярных выражений — построение Томпсона[англ.] является алгоритмом для преобразования регулярного выражения в НКА, который может эффективно распознавать шаблон строк. Обратно, алгоритм Клини[англ.] можно использовать для преобразования НКА в регулярное выражение, размер которого в общем случае экспоненциально зависит от размера автомата.
НКА обобщён многими путями, например: недетерминированным конечным автоматом с ε-переходами, преобразователями с конечным числом состояний, автоматами с магазинной памятью, альтернирующими автоматами, ω-автоматами и вероятностными автоматами. Кроме ДКА известны другие специальные случаи НКА — однозначные конечные автоматы[англ.] (англ. unambiguous finite automata, UFA) и самопроверочные конечные автоматы[англ.] (англ. self-verifying finite automata, SVFA).