Разработка компиляторов



         

Детерминированные конечные автоматы


Определим детерминированный конечный автомат как частный случай общего (недетерминированного) конечного автомата и введем некоторые дополнительные определения и соглашения, которые пригодятся нам в дальнейшем:

Определение. Автомат называется детерминированным, если множество содержит не более одного состояния для любых , . Если

всегда содержит ровно одно состояние (т.е. не имеет неопределенных переходов), то автомат называется полностью определенным .

Определение. Слово над алфавитом

допускается конечным автоматом , если существует последовательность состояний такая, что для .

Определение. Язык L распознается конечным автоматом, если каждое слово языка L допускается этим конечным автоматом.

Обозначение. Конечные автоматы удобно иллюстрировать с помощью диаграмм переходов , см. примеры ниже (двойным кружком обозначены конечные состояния):

Автомат, распознающий язык : Автомат, распознающий язык

:




Содержание  Назад  Вперед