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

В основе построения недетерминированного конечного автомата-распознавателя лежит допущение о возможности перехода по определённому входному сигналу сразу в несколько состояний. В такой момент происходит своеобразное «расщепление» реальности: если переход по сигналу a возможен в состояния si и sj, то допускается, что в одном из «миров» автомат перешёл в состояние si и продолжил свою работу, в другом «мире» состоялся переход в sj.

В данном параграфе демонстрируется, что любой недетерминированный конечный автомат (НКА) эквивалентен некоторому обычному детерминированному автомату (ДКА). Основная причина интереса к НКА – их более простой и компактный вид для многих задач распознавания.

Определение 17. Недетерминированным конечным автоматом-распознавателем называется пятёрка объектов A=S, X, S0, δ, F, где:

S – конечное непустое множество состояний;

X – конечное непустое множество входных сигналов;

S0⊆ S – множество начальных состояний;

δ: S× X⟶ 2S – функция переходов (2S – булеан множества S);

F⊆ S – множество финальных состояний.

Как видим, разница в определениях НКА и ДКА заключается в виде функции переходов.

Если разрешить в автомате не только переход по одному сигналу во множество состояний, но и переход в новое состояние по пустой строке, получим недетерминированный автомат с ε -переходами.

Определение 18. НКА с ε -переходами называется пятёрка объектов Aε =S, X, S0, δ, F, где:

S – конечное непустое множество состояний;

X – конечное непустое множество входных сигналов;

S0⊆ S – множество начальных состояний;

δ: S× X∪ ε ⟶ 2S – функция переходов;

F⊆ S – множество финальных состояний.

Как определить для недетерминированных автоматов основное понятие – «распознавание входной цепочки»? Подход, который принят в теории формальных языков, состоит в следующем.

Определение 19. Недетерминированный конечный автомат распознает входную цепочку α, если существует путь, помеченный символами цепочки α, из начального в одно из заключительное состояний автомата, возможно, с учетом спонтанных переходов. Недетерминированный конечный автомат распознает язык L, если он распознает все цепочки этого языка, и только их.

Рассмотрим примеры НКА. Пусть V={a, b, c}, L – все цепочки, содержащие подстроку abc. НКА, распознающий язык L, представлен на рис. 13.

Рис. 13. Недетерминированный конечный автомат.

Следующий НКА с ε -переходами будет использоваться в дальнейших примерах.

Рис. 14. Недетерминированный конечный автомат с ε -переходами.

Теорема 8. Для любого недетерминированного конечного автомата-распознавателя существует эквивалентный ему детерминированный конечный автомат-распознаватель.

Доказательство этой теоремы проведём конструктивно, то есть предложим алгоритм построения по заданному НКА эквивалентного ему ДКА. Сначала покажем, как НКА с ε -переходами привести к НКА без ε -переходов, а потом – как для НКА без ε -переходов построить эквивалентный ему детерминированный автомат, допускающий тот же язык.

Пусть Aε =S, X, S0, δ, F – НКА с ε -переходами. Будем строить НКА A – эквивалент Aε, но без ε -переходов.

Определение 20. ε -замыканием состояния s∈ S, обозначаемым Ξ (s), называется множество всех состояний, которые достижимы из s без подачи входного сигнала.

Множеству Ξ (s) принадлежит само состояние s и все те состояния, которые достижимы из s по ε -переходами. Для автомата, изображённого на рис. 14:

Ξ s0=s0, s1, Ξ s1=s1, Ξ (s2)={s2}, Ξ (s3)={s3, s2}.

Множеством состояний автомат A являются ε -замыкания состояний Aε. Начальными состояниями A будут ε -замыкания начальных состояний Aε. Множеством заключительных состояний A будут такие ε -замыкания, в которые входят заключительные состояния Aε.

Функция переходов δ автомата A определяется по следующей формуле:

δ AΞ s, a=q∈ Ξ sΞ δ Aε q, a.

С учётом вышесказанного, определим для автомата A, эквивалентного автомату, изображённому на рис. 14, таблицу переходов. Начальным состоянием нового автомата будет состояние q0, заключительным состоянием – q3.

Рис. 15. Недетерминированный конечный автомат без ε -переходов.

Рассмотрим теперь алгоритм построения по заданному недетерминированному автомату AH=S, X, Q0, δ H, FH без ε -переходов эквивалентного ему детерминированного автомата. В качестве состояний детерминированного автомата следует выбрать булеан множества S. Начальным состоянием будет элемент из 2S, соответствующий Q0. Множество F заключительных состояний искомого автомата состоит из всех таких множеств состояний, которые включают хотя бы одно заключительное состояние исходного автомата. Функция переходов δ Д детерминированного автомата определяется следующим образом:

∀ Q⊆ S, ∀ a∈ X δ ДQ, a=s∈ Qδ H s, a.

В случае нашего примера множество состояний будет содержать 16 элементов: ∅, {q0}, {q1}, q2, {q3}, {q0 q1}, {q0q2}, …, {q0 q1 q2 q3}. Начальным состоянием будет состояние {q0 q1}. Финальными будут все состояния, которые содержать q3. И, например,

δ Д ({q0 q2}, a)=δ H (q0, a)∪ δ H(q2, a)={q2 q3}∪ {q3}={q2q3}.

После того, как детерминированный автомат построен, можно выполнить его минимизацию. Для нашего примера после минимизации получим автомат, показанный на рис. 16.

Рис. 16. ДКА, построенный по недетерминированному автомату.

Вопросы и упражнения.

Преобразуйте следующие НКА в ДКА. Начальные состояния помечены стрелкой, конечные – звёздочками.