[21.03.11] Лекция №7 (1061967)

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

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

Лекция №7 [21.03.11]

Более развесистый пример:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

удаляем -правила:

- всё, больше нетерминалов нет

получилось:

- здесь можно, потому что стартовая

- здесь уже не надо, оно удаляется

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

, ,

, ,

, ,

теперь грамматику без цепных правил:

, , , , поэтому

3. Удаление бесполезных символов

Нетерминальный символ КС-грамматики называется бесполезным, если из него не выводится ни одна терминальная цепочка, то есть, не существует такого ,

Бесполезный символ может быть удалён из исходной грамматики вместе со всеми правилами, в которые он входит, без изменения языка, порождаемого этой грамматикой.

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

Алгоритм удаления бесполезных символов:

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

Множество состоит из таких нетерминалов , что:

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

- общая формула

В силу конечности множества нетерминалов грамматики, алгоритм содержит конечное количество шагов.

Множество бесполезных символов – это , - usual (полезные).

Пример:

тогда:

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

Такие дела.

Ещё пример:

и тогда останется:

С помощью приведённого алгоритма может быть решена проблема пустоты для КС-грамматики. Проблема формулируется следующим образом: выяснить, пуст ли язык, порождаемый данной грамматикой.

Если в результате анализа выяснится, что , то это означает, что язык пустой.

4. Удаление недостижимых символов

Символ в объединённом алфавите называется недостижимым, если из аксиомы грамматики не выводится ни одна цепочка, содержащая вхождение символа .

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

Графом КС-грамматики называется ориентированный граф, множество вершин которого есть объединение , а множество дуг определяется следующим образом: дуга ведёт из вершины в вершину тогда и только тогда, когда правило , где и - некоторые цепочки в объединённом алфавите.

Для выявления недостижимых вершин, выполним поиск в ширину для вершины, помеченной стартовой.

0
0	1	1		1	1

- недостижим из стартовой .

Таким образом, преобразование КС-грамматики к специальному виду осуществляется в четыре этапа:

1) удаление -правил;

2) удаление цепных правил;

3) удаление бесполезных символов;

4) удаление недостижимых символов;

-) Удаление аксиомы из правой части

Для решения этой задачи достаточно ввести новый нетерминал (несовпадающий с существующими):

- аксиома

Пример:

после указанного преобразования в грамматике появились -правило и цепное правило. Будем их удалять:

1)

- вот и пропала

2)

И вот последние две строки – это теперь множество правил в нашей грамматике. Бесполезных и недостижимых символов нет.

Это типичная задача из аттестации, которая будет в мае, кстати.

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

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

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

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

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

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