существует пары состояний hq
1
, q
2
i, такой что тройка hq
1
, e, q
2
i принадле-
жит ∆.
Недетерминированные автоматы также, как и детерминированные, в
ходе своей работы последовательно, буква за буквой, читают подавае-
мые им на вход слова и в зависимости от последней прочитанной буквы
меняют свое состояние. Предположим, что в какой-то момент времени
автомат находится в состоянии q и читает букву x. Если существуют
какие-то состояния, в которые автомат может перейти из состояния q
под действием буквы x, то он выбирает одно из них и переходит в него.
Если таких состояний нет, то он ”зависает”, то есть переходит в неопре-
деленное состояние и перестает читать какие-либо дальнейшие символы.
Кроме того, он может в любой момент, не читая никакого символа, совер-
шить скачок из одного состояния в другое, если такой скачок возможен
(т. е. на диаграмме есть стрелка, помеченная символом e, которая ведет
из первого состояния во второе).
Недетерминированные автоматы, аналогично детерминированным,
служат для распознавания слов. Мы говорим, что автомат распознает
слово, если он, стартуя из начального состояния и прочитав данное сло-
во может, следуя описанным выше правилам, остановится в одном из ко-
нечных состояний и при этом не ”зависнуть”. Другими словами, можно
считать, что недетерминированный конечный автомат обладает опреде-
ленной ”интуицией”; читая слово, он на некотором шаге в процессе чтения
может встать перед выбором из нескольких альтернатив: некоторые из
вариантов выбора могут привести его в одно из конечных состояний, а
некоторые — нет. Автомат, как бы предвидя исход своей работы, всегда
выбирает одну из тех альтернатив, которые могут привести его в одно
из конечных состояний. Если же все варианты одинаково плохи, то он
выбирает какой-то один из них, неважно какой.
Дадим формальное определение. Мы говорим, что недетерминиро-
ванный конечный автомат hQ, Σ, ∆, s, F i может перейти из состояния
q ∈ Q в состояние p ∈ Q под действием слова w ∈ Σ
∗
, если существу-
ет конечная последовательность q
0
, q
1
, . . . , q
n
элементов из Q и функция
t : {0, . . . , n} → N, такие что q
0
= q, q
n
= p, t(0) = 0, t(n) = |w| и для
каждого i < n либо t(i + 1) = t(i) и hq
i
, e, q
i+1
i ∈ ∆, либо t(i + 1) = t(i) + 1
и hq
i
, (w)
t(i+1)
, q
i+1
i ∈ ∆.
Соотнося это формальное определение с данным выше неформаль-
ным, можно сказать, что q
0
, . . . , q
n
— это последовательность состояний,
которые автомат проходит, читая слово w, а t(i) — это количество букв
24