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

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

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

Определение. Слово w = a₁…a_k над алфавитом Σ допускается конечным автоматом M = (Q, Σ, δ, q ₀, F), если существует последовательность состояний q₁, q₂,..., q_n такая, что q₁ = q₀, и для .

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

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

Автомат, распознающий язык (aa*|bb*): Автомат, распознающий язык (a|b)*abb: