Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Алгоритм построения МП-автомата по произвольной КС-грамматике




Эквивалентность МП-автоматов и КС-грамматик

Лемма: Для любой КС-грамматики можно построить соответствующий
МП-автомат и наоборот.

 

Построим естественный (недетерминированный) «нисходящий» распознаватель, эквивалентный данной КС-грамматике.

Вход: - произвольная КС-грамматика.

Выход: - МП-автомат, допускающий цепочки опустошением магазина, такой, что .

Метод:

1. Множество состояний МП-автомата примет вид ;

2. Входной алфавит МП-автомата совпадает с алфавитом терминальных символов исходной грамматики;

3. Алфавит магазинных символов будет следующим ;

4. Начальным состоянием будет единственное состояние, т.е. ;

5. Начальным магазинным символом будет целевой символ КС-грамматики ;

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

7. Определим множество результирующего МП-автомата следующим образом:

a. Если множество правил исходной грамматики содержит правило вида , , , то во множество функций перехода автомата добавляется функция перехода вида для , , ;

b. Во множество функций перехода автомата добавляются все переходы вида для , .

 

Пример:

1. Построить МП-автомат, распознающий язык, заданный множеством , и порождающийся КС-грамматикой с правилами вида ;

2. Построить последовательность тактов работы МП-автомата для цепочек , .

Решение:

1. МП-автомат будет иметь вид

где функции перехода будут следующие

,

,

.

2. Теперь построим последовательность тактов работы автомата для различных цепочек

a. Последовательность тактов работы автомата для цепочки будет иметь вид

b. Последовательность тактов работы автомата для цепочки будет иметь вид

 

Домашнее задание: П остроить для нижеследующей грамматики МП-автомат

.

И построить последовательность тактов работы МП-автомата для цепочки

.

Домашнее задание (убрать в практику): П остроить для нижеследующей грамматики МП-автомат

,

где

.

И построить последовательность тактов работы МП-автомата для цепочки

.

 

Тип синтаксического анализа, проводимого для КС-грамматики МП автоматом, построенном выше, называется «нисходящим анализом» («анализом сверху вниз») или «предсказывающим анализом», потому что при этом дерево вывода строится по существу сверху (от корня) вниз, а каждый такт вида можно трактовать как предсказание очередного шага левого вывода.

Можно построить расширенный МП-автомат, который работает «сверху-вниз» как «восходящий анализатор», моделируя в обратном порядке правые выводы в КС-грамматике.

По произвольной КС-грамматике можно построить эквивалентный расширенный МП-автомат . Здесь удобно представить себе магазин в виде цепочки, верхним символом которой является самый правый, а не самый левый символ. В силу этого соглашения конфигурации расширенного МП-автомата определяются точно так же, как и раньше, а отношение несколько иначе. Если , то будем писать для , .

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

 

Лемма: Для любой КС-грамматики можно построить соответствующий
расширенный МП-автомат и наоборот.

 




Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 7506; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.