Конечный автомат: различия между версиями

[отпатрулированная версия][отпатрулированная версия]
Содержимое удалено Содержимое добавлено
м подстановка даты в шаблон:Нет источника
Строка 1:
'''Коне́чный автома́т''' (КА) — [[абстрактный автомат]], число возможных внутренних состояний которого [[конечное множество|конечно]]. Переход из состояния в другое состояние КА производит от внешнего воздействия или самопроизвольно.
 
Примерами физической реализации КА могут служить любые цифровые системы, например, компьютеры или некоторые логические узлы компьютеров — [[триггер]]ы и другие устройства. Комбинационная последовательная логика не может являться КА, так как не имеет внутренних состояний.
 
С абстрактной точки зрения КА изучает раздел [[Дискретная математика|дискретной математики]] — ''теория конечных автоматов''.
Строка 8:
 
== Формальное описание конечного автомата ==
 
=== Общее описание ===
Существуют различные способы задания алгоритма функционирования конечного автомата. Например, конечный автомат может быть задан в виде упорядоченной пятерки элементов некоторых [[Множество (математика)|множеств]]:
 
Строка 81 ⟶ 82 :
Если рассмотреть случай, когда автомат формально задан следующим образом: <math>M = (V, Q, S, F, \delta)</math>, где <math>S</math> — множество ''начальных состояний'' автомата, такое, что <math>S \subseteq Q</math>, то появляется третий признак недетерминированности — наличие нескольких начальных (стартовых) состояний у автомата <math>M</math>.
 
''Теорема о детерминизации''{{источникНет АИ|11|6|2020}} утверждает, что для любого конечного автомата может быть построен эквивалентный ему детерминированный конечный автомат (два конечных автомата называют эквивалентными, если их языки совпадают{{пояснить}}). Однако поскольку количество состояний в эквивалентном ДКА в худшем случае растёт [[Экспоненциальный рост|экспоненциально]] с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, [[конечный автомат с выходом|конечные автоматы с выходом]] в общем случае не поддаются детерминизации.
 
В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА{{источникНет АИ|11|6|2020}}.
 
== Автоматы и регулярные языки ==