[16.05.11] Лекция №12 (Конспекты - Теория формальных языков)

Лекция №12 [16.05.11]

Вспомним, что мы делаем вообще: нам надо сделать такой автомат, чтобы соответствующий вывод цепочек был без тупиков.

и надо найти, существует ли

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

Если есть аксиома, и за некоторое количество шагов мы получаем , а потом есть и , то надо выбрать, по какому пути пойдём. А нам известно, это первый нетерминал, который нам встречается при анализе, и естественно .

Короче, это разветвление у МП-автомата выглядит так: - верхний символ магазина. И мы будем типа подсматривать на ленту вперёд, но на фиксированную длину.

И вот мы сформулировали -условие: , , , , , если это всё, то: , оно КС-грамматика. Как-то так.

Пример:

В прошлый раз мы установили, что эта грамматика не является

Проверим, будет ли она . Для проверки условия достаточно для каждого нетерминала грамматики проделать следующее:

1) вычислить все такие цепочки и все такие, что имеет место левая выводимость ;

2) зафиксировав левый контекст для каждой пары правил , вычислить -множество и для всех и убедиться в том, что их пересечение пусто;

Что можно получить из нетерминала ?

(само себя), тогда ,

теперь множество двухбуквенных префиксов (первые два уже фиксированные, тут хоть как крутись, будут только они два)

и второе

пересечение первого ( ) и второго ( ) – пустое. Условие пока что выполняется.

идём дальше: , здесь ,

теперь и и пересечение почему-то опять пусто.

далее:

и для , пересечение опять пусто.

Для любого из того, что выводится следует, что для любого пересечение -множеств является пустым.

Теперь будем разбираться с нетерминалом :

, тут ,

если , то

первое

второе

их пересечение вновь пусто. Но это ещё не всё, потому что надо для всех возможных.

первое

второе

пересечение пустое.

Таким образом, -условие для данной грамматики выполнено, и, следовательно, данная грамматика является -грамматикой.

Возможные аванцепочки (цифры – номера правил из самого начала примера)

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

-грамматика, для которой номер применяемого на каждом шаге правила определяется только нетерминалом и аванцепочкой, но не зависит от (от левого контекста, иначе говоря), называется сильной -грамматикой.

Вот пример по применению этой таблицы:

- верхний символ магазина

- содержимое выходной цепочки, на которой будут записываться номера применяемых правил

вспомним правила МП-автомата:

где над выводом цифра – это сколько шагов мы делали правила МП, по удалению повторных в

- восстановили исходную. Йощь.

А вот возьмём цепочку, не принадлежащую нашему языку:

В общем случае, учёт левого контекста (цепочки ) не ведётся.

Пример:

Эта грамматика конечна. Почему-то. Построим деревья вывода.

Проверим, что данная грамматика является -грамматикой:

Для нетерминала :

, то ,

пересечение пустое.

Для нетерминала :

1) , то ,

2) , то ,

1) и . Пересечение пусто.

2) и . Пересечение пусто.

Эта грамматика является -грамматикой, но не является сильной, потому что нужно учитывать левый контекст.

Последняя строчка, кстати, показывает, что данная грамматика не является -грамматикой.

Ещё пример:

Рассмотрим грамматику, которая не является -грамматикой ни при каком

По фиксированному заранее количеству букв невозможно определить, какое правило (1 или 2) надо применять на первом шаге. Поскольку слова могут быть достаточно длинными.