КС-грамматика. Дерево вывода. Однозначность

Определения

КС-грамматика

• Контекстно-свободная грамматика
• Контекстно-свободный язык
• Праволинейная грамматика (?)

Дерево вывода

• Дерево вывода слова

Однозначность

• Однозначная грамматика
• Однозначный язык

Теоремы/свойства

КС-грамматики

• Теорема. Связь рациональных языков с языками, порождаемыми праволинейными грамматиками
• Возможно потребуется доказать, что Язык $L=a^n{b}^n{c}^n,n\in \mathbb{N}$ не является контекстно-свободным

Деревья вывода

• Вопрос ЛОИ. Однозначно ли можно восстановить вывод по дереву вывода
• Вопрос ЛОИ. Однозначно ли можно восстановить дерево вывода по цепочке
• Связь вывода цепочки и дерева вывода цепочки

Однозначность

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

Опечатки?