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