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