06-07-2023
Конечный автомат — абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.
Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: , где:
Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».
Конечные автоматы широко используются на практике, например в синтаксических, лексических анализаторах, и тестировании программного обеспечения на основе моделей.
Содержание |
Конечные автоматы подразделяются на детерминированные и недетерминированные.
Существуют переходы, помеченные пустой цепочкой ε | Из одного состояния выходит несколько переходов, помеченных одним и тем же символом |
---|---|
|
|
Если рассмотреть случай, когда автомат задан следующим образом: , где:
Тогда появляется третий признак недетерминизма - наличие нескольких начальных (стартовых) состояний у автомата .
Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.
В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.
Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет — так называются слова, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.
Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.
В SFC программа описывается в виде схематической последовательности шагов, объединенных переходами.
Конечный автомат.