[05.03.11] Лекция №5 (Конспекты - Теория формальных языков)
Описание файла
Файл "[05.03.11] Лекция №5" внутри архива находится в следующих папках: Конспекты - Теория формальных языков, 5 - [05.03.11] Лекция №5. Документ из архива "Конспекты - Теория формальных языков", который расположен в категории "". Всё это находится в предмете "теория формальных языков" из 6 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "теория формальных языков" в общих файлах.
Онлайн просмотр документа "[05.03.11] Лекция №5"
Текст из документа "[05.03.11] Лекция №5"
Лекция №5 [05.03.11]
Контекстно свободные языки и грамматики
Контекстно свободной грамматика – множество правил которой имеет вид:
этому выводу сопоставим дерево вывода:
- корень данного дерева – стартовая аксиома;
- вершины дерева помечаются символами объединённого алфавита или пустой цепочки;
- метки листьев образуют цепочку, полученную в результате данного вывода;
Данное дерево, кроме этого, является упорядоченным – в нём соответствующие символы записываются так, чтобы полученные в результате вывода цепочки в этом дереве можно было читать слева направо.
Кроме общего дерева вывода можно рассматривать частичное дерево вывода из некоторого нетерминала цепочки в объединённом алфавите -
Дерево называется кустом, если его высота равна 1 -
Дерево называется -свободным, если среди меток его листьев нет пустой цепочки.
Пусть - некоторое помеченное дерево и - тоже.
Дерево вывода цепочки в объединённом алфавите из нетерминала в КС-грамматике - это помеченное дерево, метками вершин которого являются символы объединённого алфавита или пустая цепочка, которое строится по следующим правилам:
1) дерево любого вывода длины 0 состоит из единственной вершины, помеченной нетерминалом ;
3) дерево вывода из нетерминала в непустую цепочку за один шаг - есть дерево ;
4) если - это некоторая цепочка в объединённом алфавите и - дерево некоторого вывода этой цепочки из нетерминала , где и для , , и в множестве правил вывода есть , то дерево …[куча ещё какой-то фигни]… что его последний шаг имеет вид ,
Все выводы данной цепочки из фиксированного нетерминала, по которым приведённая процедура даёт одно и то же дерево вывода, будем называть эквивалентными. Среди эквивалентных выводов выделяют:
1) левый вывод – на каждом шаге заменяется самое левое вхождение нетерминального символа;
2) правый вывод – на каждом шаге заменяется самое правое вхождение нетерминального символа;
Левый вывод:
Правый вывод:
В данном случае эти два вывода являются эквивалентными и различаются между собой только порядком применения правил.
Однозначность КС-грамматик
КС-грамматику называют однозначной, если каждая цепочка, порождаемого ей языка, имеет единственное дерево вывода. Или (единственный левый / единственный правый) вывод.
Пример неоднозначной грамматики:
- произвольное логическое условие, - произвольный оператор
Исправим грамматику, чтобы она стала однозначной:
И вот в этой уже грамматике существует только единственное дерево вывода предложенного предложения.