[05.03.11] Лекция №5 (1061958)

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

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

Лекция №5 [05.03.11]

Контекстно свободные языки и грамматики

Контекстно свободной грамматика – множество правил которой имеет вид:

, ,

Рассмотрим грамматику

(1)

(2)

(3)

(4)

(5)

(6)

(7)

этому выводу сопоставим дерево вывода:

- корень данного дерева – стартовая аксиома;

- вершины дерева помечаются символами объединённого алфавита или пустой цепочки;

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

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

Кроме общего дерева вывода можно рассматривать частичное дерево вывода из некоторого нетерминала цепочки в объединённом алфавите -

Дерево называется кустом, если его высота равна 1 -

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

Пусть - некоторое помеченное дерево и - тоже.

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

1) дерево любого вывода длины 0 состоит из единственной вершины, помеченной нетерминалом ;

2) дерево из в имеет вид ;

3) дерево вывода из нетерминала в непустую цепочку за один шаг - есть дерево ;

4) если - это некоторая цепочка в объединённом алфавите и - дерево некоторого вывода этой цепочки из нетерминала , где и для , , и в множестве правил вывода есть , то дерево …[куча ещё какой-то фигни]… что его последний шаг имеет вид ,

из с .

Все выводы данной цепочки из фиксированного нетерминала, по которым приведённая процедура даёт одно и то же дерево вывода, будем называть эквивалентными. Среди эквивалентных выводов выделяют:

1) левый вывод – на каждом шаге заменяется самое левое вхождение нетерминального символа;

2) правый вывод – на каждом шаге заменяется самое правое вхождение нетерминального символа;

Левый вывод:

Правый вывод:

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

Однозначность КС-грамматик

КС-грамматику называют однозначной, если каждая цепочка, порождаемого ей языка, имеет единственное дерево вывода. Или (единственный левый / единственный правый) вывод.

Пример неоднозначной грамматики:

- произвольное логическое условие, - произвольный оператор

:

кочующее

Исправим грамматику, чтобы она стала однозначной:

)

И вот в этой уже грамматике существует только единственное дерево вывода предложенного предложения.

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

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

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

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

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

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