Разработка компиляторов
Детерминированные конечные автоматы
Определим детерминированный конечный автомат как частный случай общего (недетерминированного) конечного автомата и введем некоторые дополнительные определения и соглашения, которые пригодятся нам в дальнейшем:
Определение. Автомат называется детерминированным, если множество содержит не более одного состояния для любых , . Если
всегда содержит ровно одно состояние (т.е. не имеет неопределенных переходов), то автомат называется полностью определенным .
Определение. Слово над алфавитом
допускается конечным автоматом , если существует последовательность состояний такая, что для .
Определение. Язык L распознается конечным автоматом, если каждое слово языка L допускается этим конечным автоматом.
Обозначение. Конечные автоматы удобно иллюстрировать с помощью диаграмм переходов , см. примеры ниже (двойным кружком обозначены конечные состояния):
Автомат, распознающий язык : Автомат, распознающий язык
:
