Переход от НДА к ДА

Недетерминированные конечные автоматы-распознаватели

Определение НДА

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

1) - переход, где - пустой символ

Это означает, что автомат в какой-то момент времени при условии, что он находился в состоянии , спонтанно, без подачи на вход какого-либо символа перейти в состояние .

2)

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

3) наличием несколько начальных состояний,

Недетерминированный автомат (НДА) - это автомат, где значение функции переходов d - не отдельное состояние, как в детерминированном автомате (ДА), а множество состояний. В общем случае у НДА может быть также не одно, а множество начальных состояний (если начальное состояние не единственно, то эти состояния при изображении таблицы переходов будут помечаться стрелкой).

Способ представления конечных распознавателей с помощью таблицы переходов легко распространяется и на представление недетерминированных конечных распознавателей.

Необходимо сделать лишь два изменения:

- во-первых, каждый элемент таблицы может не одно состояние как в детерминированном автомате, а множество состояний. Мы указываем это множество, просто перечисляя его элементы и не заключая их в скобки.

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

Пример.

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

Рис. 2 Возможные поведения этого автомата при подаче входной цепочки abbba

-------------------------------------------------------

Пример.Пусть задан недетерминированный конечный автомат-распознаватель с ε-переходами:

Определить возможные поведения этого автомата при подаче входной цепочки bbab.

Автомат на рисунке а), находясь в начальном состоянии Q0, может без подачи входного сигнала перейти в состояние Q1. Если на его вход подать сигнал b, то из состояния Q0 автомат переходит в состояние Q2, а из состояния Q1 нет возможных путей. При подаче на вход следующего сигнала b, автомат из состояния Q2 может перейти в любое из двух состояний, Q2 и Q3, причем из состояния Q3 он может спонтанно перейти также в состояние Q2.

На рисунке b) показаны возможные поведения этого автомата при подаче входной цепочки bbаb. На этой диаграмме хорошо видно, что автомат спонтанно может выполнить переход, помеченный пустой цепочкой ε (такие переходы определены на диаграмме вертикальными ребрами), а каждый переход, помеченный входным символом, может быть выполнен только при подаче входного символа.

Распознавание входной цепочки недетерминированным автоматом-распознавателем опирается на следующие определение.

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

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

Рисунок ниже представляет детерминированный автомат, распознающий тот же самый язык, что и автомат на предыдущем рисунке. Иными словами, эти два конечных автомата эквивалентны.

Рисунок. Детерминированный автомат, эквивалентный недетерминированному автомату рисунка 1

Таким образом, в нашем примере для недетерминированного автомата существует эквивалентный ему детерминированный конечный автомат, распознающий тот же самый язык. Оказывается, что это - общее правило:

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

Переход от НДА к ДА

Переход от недетерменированного автомата к детерменированному происходит в два этапа:

1) по недетерменированному автомату строится эквивалентный ему недетерменированный автомат без ε-переходов;

2) по недетерменированному автомату без ε-переходов строится эквивалентный ему детерменированный автомат.

Рассмотрим переход от НДА к ДА на примере.

Пусть задан НДА:

Выполним первый этап.

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

ε-замыкания для некоторого состояния Q_i называют множество, включающее в себя само состояние Q_i , а также все состояния Q_j , в которые автомат может перейти под действием пустого символа ε, т.е.:

Состоянием недетерменированного автомата-распознавателя без ε-переходов будут являться ε-замыкания исходного недетерменированного автомата.

Для автомата рисунка 1:

Ξ(Q0)={Q0, Q1}=q₀,

Ξ(Q1)={Q1}=q₁,

Ξ(Q2)={Q2}=q₂,

Ξ(Q3)={Q3, Q2}=q₃.

Состояние q₃ является финальным, т.к. в его входит финальное состояние Q₃ исходного НДА.

Граф переходов этого недетерминированного автомата представлен на следующем рисунке .

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

Второй этап.

Построение эквивалентного детерменированного автомата.

Рассмотрим теперь алгоритм построения по заданному недетерминированному автомату Ан=<Q,X,Q0,δн,Fн> без ε-переходов эквивалентного ему детерминированного автомата.

Заметим, что в автомате Ан множество начальных состояний может содержать несколько состояний (в данном примере - два начальных состояния: {q0, q1}).

В качестве состояний искомого детерминированного автомата естественно выбрать множества состояний исходного недетерминированного автомата.

Множество Fд заключительных состояний искомого автомата состоит из всех таких множеств состояний, которые включают хотя бы одно заключительное состояние исходного автомата.

Введем следующие переобозначения:

Тогда:

После минимизации данного детерминированного автомата-распознавателя имеем:

Таким образом, недетерминированные автоматные распознаватели распознают то же множество языков, что и детерминированные.

Пример.

	-	-
a
b
c

:

:

:

a	→	, →{ , }	, →{ , }
b	→	, →{ , }	, →{ , }
c	→	→	, →{ , }

Граф недетерминированного автомата-распознавателя без ε-переходов:

:

:

:

:

:

:

:

:

:

Граф детерминированного автомата-распознавателя: