КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Детерминированных конечных автоматов и А-грамматик
Эквивалентность недетерминированных и
Термин недетерминированный автомат может привести в недоумение, так как в русском и других языках понятие автомата, в сущности, не позволяет применить к нему прилагательное “недетерминированный”. Недетерминированный автомат - это формализм для определения множества цепочек, обобщающий понятие конечного автомата (ни о каких случайностях, вероятностях здесь речи нет).
Недетерминированный автомат (НДА) - это автомат, где значение функции переходов 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
Дата добавления: 2015-06-27; Просмотров: 920; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |