Эквивалентность недетерминированных и детерминированных А-грамматик

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

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

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

Так автомат, представленный на рисунке 3.2, допускает цепочку 11, так как

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

,

где A - отвергающее, на это не влияет.

На рисунке 3.3 представлен еще один НДА с входным алфавитом { а, л, н, о, с, ь }, который допускает только две цепочки лассо и лань.

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

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

В общем случае, если НДА содержит n состояний, то ДА будет содержать 2 ⁿ состояний. На практике многие из этих подмножеств представляют собой недостижимые состояния.

В приведенной ниже процедуре перехода от НДА к ДА переходы строятся только для тех подмножеств, которые действительно необходимы.

Пусть М_н - НДА, а М_д - эквивалентный ему ДА. Процедура перехода от НДА к ДА задается пятью шагами.

1. Пометить первый столбец функциональной таблицы для М_д множеством начальных состояний автомата М_н. Применить к этому множеству шаг 2.

2. По данному множеству состояний X, помечающему столбец таблицы переходов М_д, для которого переходы еще не вычислены, определить те состояния М_н, которые могут быть достигнуты из X с помощью каждого входного символа a, и поместить множества последующих состояний Y_a в соответствующие ячейки таблицы М_д. Символически это выражается так: если d функция НДА, то функция ДА d ^| задается формулой

d ^| (X, a) = {y | yÎ d (x, a), для некоторого x из X}

3. Для каждого множества Y, порожденного переходами на шаге 2, определить, имеется ли уже в М_д столбец, помеченный этим множеством. Если нет, то создать новый столбец и пометить его этим множеством Y. Если множество Y уже использовалось как метка, то никаких действий не требуется.

4. Если в таблице М_д есть столбец, для которого переходы еще не вычислены, вернуться назад и применить к этому столбцу шаг 2. Если все переходы вычислены, перейти к шагу 5.

5. Пометить столбец как допускающее состояние М_д, когда он содержит допускающее состояние М_н. В противном случае пометить как отвергающее.

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

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

Пример 3.1. Пусть задана недетерминированная А-грамматика вида:

S ® aB ï aC ï bB ï bS ï c

B ® cC ï c

C ® a ï aS ï c

Эта грамматика не имеет естественного символа, ограничивающего цепочку, поэтому во всех правилах вида A ® a добавим предзаключительное состояние F^½ и получим правила A ® a F^½ .

Добавим также символ ограничения цепочки, например, ^ и правило F^½ ® ^ F, где F - заключительное состояние. В результате получим модифицированную грамматику

S ® aB ï aC ï bB ï bS ï cF^½

B ® cC ï cF^½

C ® aF^½ ï aS ï cF^½

F^| ® ^ F.

Рассматриваем для недетерминированных правил неупорядоченные безповторные достижимые подмножества множества нетерминалов и в результате получим детерминированную грамматику

S ® a< BC> ï b< BS> ï cF^½

< BC> ® a< SF^½ > ï c< CF^½ >

< BS> ® a< BC> ï b< BS> ï c< CF^½ >

< SF^½ > ® a< BC > ï b< BS> ï cF^½ ï ^ F

< CF^½ > ® a< SF^½ > ï cF^½ ï ^ F

F^½ ® ^ F.

Полученная грамматика порождает те же цепочки, что и исходная. Отметим, что дерево вывода в автоматной грамматике вырождено, и его вполне можно представлять в виде строки. Так дерево вывода цепочки acac ^ в исходной грамматике имеет вид S _a B _c C _a S _c F^½ _^ F, а в полученной детерминированной S _a < BC> _c < CF^|> _a < SF^|> _c F^½ _^ F.

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

S ® aA ï bB ï cF^½

A ® aC ï cD

B ® aA ï bB ï cD

C ® aA ï bB ï cF^½ ï ^ F

D ® aC ï cF^½ ï ^ F

F^| ® ^ F •