Примерная структура двух экзаменационных билетов,

предлагавшихся по курсу ТРЯП в 2004 г.

Вариант 1.

1. Для регулярного выражения <…> над алфавитом T = {0, 1} построить эквивалентный ДКА. По полученному ДКА построить эквивалентную праволинейную грамматику.

2. Выяснить, является ли грамматика G = {<…> } LR(k) грамматикой. Найти точное значение k и построить детерминированный правый анализатор.

3. Для грамматики G = {<…> } написать эквивалентную LL(1) грамматику. Для полученной грамматики построить LL(1) анализатор.

4. Является ли язык <…> контекстно-свободным?

5. Построить МП-автомат, распознающий язык L = {{c,b,}* \ <…> }.

Вариант 2.

1. Для грамматики G = {<…>} построить эквивалентный ДКА. По полученному ДКА построить эквивалентное регулярное выражение.

2. Выяснить, является ли грамматика G = {<…> } LR(k) грамматикой. Найти точное значение k и построить детерминированный правый анализатор.

3. Для грамматики G = {<…>} написать эквивалентную LL(1) грамматику. Для полученной грамматики построить LL(1) анализатор.

4. Является ли язык <…> регулярным?

5. Построить неукорачивающую грамматику, порождающую язык <…>.