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

В основе построения недетерминированного конечного автомата-распознавателя лежит допущение о возможности перехода по определённому входному сигналу сразу в несколько состояний. В такой момент происходит своеобразное «расщепление» реальности: если переход по сигналу 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.

	a	b
q0=Ξ(s0)={s0,s1}	{Ξ(s2),Ξ(s3)}	{Ξ(s2)}
q1=Ξ(s1)={s1}	{Ξ(s2),Ξ(s3)}	∅
q2=Ξ(s2)={s2}	∅	{Ξ(s2),Ξ(s3)}
q3=Ξ(s3)={s3,s2}	{Ξ(s0),Ξ(s3)}	{Ξ(s2),Ξ(s3)}

Рис. 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. ДКА, построенный по недетерминированному автомату.