рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Построение МП-распознавателей для q-грамматик

Построение МП-распознавателей для q-грамматик - раздел Математика, Основы ДИСКРЕТНОЙ МАТЕМАТИКИ   Кс-Грамматика (Грамматика Второго Типа) Называется Q-Граммаик...

 

КС-грамматика (грамматика второго типа) называется q-граммаикой, если правые части всех правил этой грамматики начинаются стерминальных символов и для правил с одинаковыми левыми частями множества "ВЫБОР" попарно не пересекаются.

Правила имеют вид Х -> y&, где y - терминал; & - любая це-почка терминалов и нетерминалов, возможно пустая (q-грамматика может содержать эпсилон-правил т.е. правила вида Х -> @).

Замечание: q-грамматика отличается от S-грамматики только наличием в множестве Р эпсилон-правил; этот факт существенно осложняет построение МП-распознавателя.

Дадим определение ряду унарных отношений, которые можно построить на множестве {VT, -+}.

Отношение "СЛЕД Y" (следующий за Y) - подмножество множества

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

Отношение "ВЫБОР Y" - подмножество множества входных символов МП-распознавателя, c которых могут начинаться цепочки, выводимые из нетерминала Y в любых сентенциальных формах, получаемых из множества Р правил грамматики.

Отношение "ВЫБОР Y" для конкретной грамматики строится как объединение таких отношений, построенных для всех правил, содержащих в левых частях Y.

Для правил вида Y -> x& (1) и Y -> z (2) множество "ВЫБОР Y" всегда равно первому терминалу правой части правила:

для правила 1 "ВЫБОР Y1" ={x}

для правила 2 "ВЫБОР Y2" ={z}

Если в множестве Р правил грамматики нет больше правил для нетерминала Y, то отношение "ВЫБОР Y" = "ВЫБОР Y1" U "ВЫБОР Y2"

"ВЫБОР Y" = {x,z}.

Для правил вида Y -> @ (3) отношение "ВЫБОР Y3" = "СЛЕД Y" и определять его нужно, анализируя все правила грамматики.

Для q-грамматики попарное пересечение множеств "ВЫБОР" для правил с одинаковыми левыми частями должно быть пусто. Это условие гарантирует однозначность работы МП-распознавателя (правило грамматики применяется всякий раз, когда магазинный символ является его левой частью, а входной символ принадлежит множеству

"ВЫБОР" этого правила).

 

Рассмотрим на примере процедуру проверки КС-грамматики на предмет ее принадлежности к классу q-грамматик.

Пусть задана грамматика G[S]=(VT={a,b,c}; VN={S,A}; S; P);

P={S -> aA(1); S -> b(2); A -> cSa(3); A -> @ (4)}.

Доказать, что заданная грамматика относится к классу q-грамматик.

Решение

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

1. Для нетерминала S:

"ВЫБОР S1" = {a}; "ВЫБОР S2" = {b}.

"ВЫБОР S1" П "ВЫБОР S2" = { } (пересечение пусто).

2. Для нетерминала A:

"ВЫБОР A3" = {c}; "ВЫБОР A4" = "СЛЕД A"

После нетерминала A могут следовать -+ (правило 1) и a в выводе

1 3 1 (номера правил)

S -> aA -> acSa -> acaAa ->... символ a,

отсюда "СЛЕД A" = { -+, a}.

 

"ВЫБОР A3" П "ВЫБОР A4" = {c} П {-+,a}={ }(пересечение пусто).

Вывод: заданная грамматика G[S] является q-грамматикой.

Построим для этой грамматики МП-распознаватель.

Для q-грамматики существует формальная процедура построения МП-распознавателя с одним состоянием по следующему алгоритму:

1.Входной алфавит МП-распознавателя V = {VT,-+}.

2.Множество магазинных символов { VN, VT1, /}, где VT1 часть терминальных символов грамматики, которые встречаются в цепочках & множества правил.

3.Начальная конфигурация - в магазине находится начальный символ грамматики (например для грамматики G[S] - S /).

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

4.Управляющая таблица строится так: столбцы таблицы - символы входного алфавита (последний символ -+);строки таблицы - магазинные символы. Заполнение управляющей таблицы:

а) для правил грамматики вида Х -> y& (& не пустая цепочка)

.... ¦ y ¦

............

-----+--------+----------

¦Зам.& /¦

X ¦ / ¦ ....

¦ / П¦

-----+---/---+----------

............

.... ¦ ..... ¦ ....

 

б) для правил грамматики вида Х -> y (& пустая цепочка)

.... ¦ y ¦

..............

-----+--------+----------

¦Выт.Х /¦

X ¦ / ¦ ....

¦ / П¦

-----+---/---+----------

............

.... ¦ ..... ¦ ....

В соответствии с п.п. а) и б) обрабатывается все множество Р правил грамматики (кроме эпсилон правил).

в) клетки таблицы на пересечении терминал-магазинный символ и тот же терминал-входной алфавит:

 

.... ¦ y ¦

.............

------+--------+----------

¦Выт.y /¦

y ¦ / ¦ ....

¦ / П¦

------+---/---+----------

.............

.... ¦ ..... ¦ ....

г) каждая клетка таблицы на пересечении нетерминала Z и входных символов МП-распознавателя из множества "СЛЕД Z" ={y,...-+}:

.... ¦ y ¦ .... ¦ --+ ¦

¦ ¦ .... ¦ ¦

............. .............

------+--------+--- ... ----+--------+

¦Выт.Z /¦ ¦Выт.Z /¦

Z ¦ / ¦ ¦ / ¦

¦ / Д¦ ¦ / Д¦

------+---/---+----... ----+---/---+

............. .............

.... ¦ ..... ¦ ........ ¦ ..... ¦

 

 

г) все оставшиеся клетки последнего столбца таблицы (-+) заполняются "отв."кроме клетки на пересечении со строкой /, в которой ставится "доп.";

д) оставшиеся незаполненными клетки управляющей таблицы заполняются буквой Е-"состояние ошибки".

 

Построим МП-распознаватель для языка, порождаемого G[S]

грамматикой из предыдущего примера.

 

Пусть задана q-грамматика G[S]=(VT={a,b,c}; VN={S,A}; S; P);

P={S -> aA(1); S -> b(2); A -> cSa(3); A -> @ (4)}.

 

Решение

 

1.Проверка нетерминалов на достижимость и продуктивность

 

S достижим (начальный символ); A достижим (правило 1);

 

S продуктивен (правило 2); A продуктивен (правило 1).

 

2.Построение МП-распознаватель(ранее доказано, что это q-грамматика):

- входной алфавит V={a,b,c,-+};

 

- множество магазинных символов {S,A,a,/};

 

- начальное содержимое магазина S,/;

 

- управляющая таблица имеет вид:

г======T========T========T========T========¬

¦ ¦ a ¦ b ¦ c ¦ -+ ¦

¦------+--------+--------+--------+--------¦

¦ / ¦ E ¦ E ¦ E ¦ доп. ¦

¦ ¦ ¦ ¦ ¦ ¦

¦------+--------+--------+--------+--------¦

¦ ¦ Зам. /¦ Выт. /¦ ¦ ¦

¦ S ¦ А / ¦ S / ¦ Е ¦ отв. ¦

¦ ¦ / П¦ / П¦ ¦ ¦

¦------+---/---+---/---+--------+--------¦

¦ ¦ Выт. /¦ ¦ Зам. /¦ Выт. /¦

¦ A ¦ А / ¦ Е ¦ Sa / ¦ А / ¦

¦ ¦ / Д¦ ¦ / П¦ / Д¦

¦------+---/---+--------+---/---+---/---¦

¦ ¦ Выт. /¦ ¦ ¦ ¦

¦ a ¦ а / ¦ Е ¦ Е ¦ отв. ¦

¦ ¦ / П¦ ¦ ¦ ¦

L======¦===/===¦========¦========¦========-

Примечание: поле для состояний осталось незаполненным, т.к. заполнять его нет смысла (состояние только одно).

3.Проверка работы МП-распознавателя.

Получим цепочку на основании правил грамматики:

1 3 1 3 1 4

S -> aA -> acSa -> acaAa -> acacSaa -> acacaAaa -> acacaaa

Работу МП-распознавателя по разбору цепочки acacaaa представим в виде таблицы:

-----------T-----------T---------T----------T---------T---------¬

¦Необработ.¦ Обраб. вх.¦Верх.симв¦Содержимое¦Действие ¦Действие ¦¦цепочка ¦ символ ¦магазина ¦магазина ¦с магаз. ¦с вх.симв¦

+--------T-+-----------+---------+----------+---------+---------+

¦acacaaa-+ ¦ a ¦ S ¦ S / ¦ Зам. A ¦ П ¦

¦ cacaaa-+ ¦ c ¦ A ¦ A/ ¦ Зам. Sa¦ П ¦

¦ acaaa-+ ¦ a ¦ S ¦ Sa/ ¦ Зам. A ¦ П ¦

¦ caaa-+ ¦ c ¦ A ¦ Aa/ ¦ Зам. Sa¦ П ¦

¦ aaa-+ ¦ a ¦ S ¦ Saa/ ¦ Зам. A ¦ П ¦

¦ aa-+ ¦ a ¦ A ¦ Aaa/ ¦ Выт. А ¦ Д ¦

¦ аa-+ ¦ a ¦ а ¦ aa/ ¦ Выт. а ¦ П ¦

¦ а-+ ¦ а ¦ а ¦ а/ ¦ Выт. а ¦ П ¦

¦ -+ ¦ -+ ¦ / ¦ / ¦допустить¦ - ¦

L----------+-----------+---------+----------+---------+----------

Контрольная цепочка распознается построенным МП-распознавателем.

 

 

– Конец работы –

Эта тема принадлежит разделу:

Основы ДИСКРЕТНОЙ МАТЕМАТИКИ

МЕЖДУНАРОДНОГО НАУЧНО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Условные обозначения, принятые в конспекте лекций
  N - множество всех натуральных чисел (N = {1,2,3,...}); Nо - множество всех натуральных чисел и ноль (Nо={0,1,2,3,...}); ї - знак принадлежности (" а ї А &quo

Действия с цепочками
Для цепочек допустимы следующие действия а) конкатенация (сцепление) цепочек: x = aba, y = cab; xy = abacab; б) возведение цепочек в степень: x=ab; (х)^1 = ab; (

Число элементов множества
  Для любого конечного множества М, число элементов (мощность множества) будем обозначать n(M). Пусть задано несколько множеств (подмножеств универсального множества): А,В,С,

Свойства бинарных отношений
Симметричность. Отношение R называется симметричным, если для любого элемента этого отношения (х,y) в множестве R есть соответствующая пара (y,x). Другими словами, есл

Простые высказывания; логические связки
  Простые высказывания будем обозначать p, q, r, ...Основное свойство простого высказывания: высказывание может быть или ложно(False, 0, "Hет") или истинно(True,1, "Да&

Составные высказывания; таблицы истинности
  Используя простые высказывания, логические связки(операции) и скобки, которые меняют порядок выполнения действий, можно строить составные высказывания (наибольший приоритет при выпо

Логические законы
  Пример 2 Построить таблицу истинности для В = ~(p -> q) / q.   Таблица истинности ----T---T----T--------T----------¬ ¦ p ¦ q ¦p->q¦~(p

Отношения между высказываниями
  Как было сказано выше, высказывание (простое или составное) полностью характеризуется таблицей истинности (число строк в этой таблице определяется по формуле 2^n, где n - количество

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

Общие понятия и определения
  Граф G как математический объект - это совокупность двух множеств: непустого множества вершин V и множества ребер E, элементы которого представляет собой неупорядоченные (для ориент

Элементы графов
  Граф без кратных ребер называют полным, если каждая пара вер- шин соединена ребром. Граф H называют частью графа G, если множество вершин графа H принадле

Диаметр, радиус и центр графа
  Задан единичный связный неориентированный граф G. Минимальная длина простой цепи с началом V' и концом V" называется расстоянием между этими вершинами d(V',V").

Параметры протяженности (диаметр, радиус и центр) графа
  Задан единичный связный неориентированный граф G. Максимальная длина простой цепи с началом V' и концом V" называется протяженностью между этими вершинами g(V',V").

Конечные автоматы - распознаватели
  Конечный автомат(в дальнейшем КА) - абстрактное вычислительное устройство с фиксированным и конечным объемом памяти, которое на входе читает цепочки(последовательности символов неко

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

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

Недетерминированный конечный автомат
  Недетерминированный конечный автомат (в дальнейшем НКА) представляет собой обычный КА с той разницей, что в таблице переходов паре входной символ - состояние ставится в соответствие

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

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

Задачи на построение МП-распознавателей.
Таблица 1 г========T=============================================¬ ¦ N п/п ¦ Построить МП-распознаватель для следующих ¦ ¦ ¦ регулярных множеств ¦ ¦--------+----

Задачи на построение МП-трансляторов
Таблица 2 г=========T=============================================¬ ¦ N п/п ¦ Построить МП-транслятор, который преобразует¦ ¦ ¦ цепочку А в цепочку В. ¦ ¦-------

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

Достижимых) нетерминалов
  В множестве Р правил грамматики G непродуктивным называют нетерминал из которого нельзя получить цепочку терминалов. Для поиска в множестве правил непродуктивных нетерминалов исполь

Изменение направления рекурсии
  Для построения распознавателей в правилах грамматики не должно быть левосторонней рекурсии, т.е. правил вида A -> Ax. Пусть в исходной грамматике есть следующее правило: A ->

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

Построение КА-распознавателей для праволинейных грамматик
Праволинейной называется контекстно-свободная грамматика, вправых частях правил которой имеется не более одного нетерминала и этот нетерминал заканчивает правило. В праволинейных грамматиках допуск

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги