[16.05.11] Лекция №12 (1061994)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция №12 [16.05.11]

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

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

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

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

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

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

Пример:

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

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

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

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

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

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

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

и второе

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

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

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

далее:

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

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

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

, тут ,

если , то

первое

второе

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

первое

второе

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

, то ,

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

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

1) , то ,

2) , то ,

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

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

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

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

Ещё пример:

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

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

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

Список файлов лекций