Префект
Во всем виноват - староста.
Вопросы к экзамену по курсу «Лингвистические основы информатики»
Весенний семестр, 2009 г.

1. КС-грамматики и языки. Вывод. Дерево вывода. Левосторонний и правосторонний вывод. Неоднозначные грамматики и языки.
2. Теорема о подстановке и ее следствия.
3. Теорема о накачке и ее следствия.
4. Теорема об Е-свободной грамматике.
5. Распознавание КС-языков методом динамического программирования.
6. Преобразования КС-грамматик: устранение левой рекурсии, левая факторизация.
7. МП-автоматы. Варианты распознавания. ДМПА и НМПА, их неэквивалентность.
8. Распознаваемость КС-языков МП-автоматами.
9. Идея синтаксического анализа. Два способа анализа. Использование МП-автомата для нисходящего анализа.
10. Множества FIRSТ, FОLLОW и SЕLЕСT. Алгоритмы их построения.
читать дальше