Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




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

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

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

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

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

,

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

 

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

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

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

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

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

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

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

2. По данному множеству состояний X, помечающему столбец таблицы переходов Мд, для которого переходы еще не вычислены, определить те состояния Мн, которые могут быть достигнуты из X с помощью каждого входного символа a, и поместить множества последующих состояний Ya в соответствующие ячейки таблицы Мд. Символически это выражается так: если 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

 


Поделиться:

Дата добавления: 2014-11-13; просмотров: 109; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты