2008 вариант 1, 2, 3 (Экзамен. Варианты заданий и ответы)

Вариант 1_2008ФИО____________________________________________1231. Дана грамматика G:S → BcS → aScdaBccd → aCcdaC → aCaC→a(a) Классификация:найти такое целое k, чтоG является грамматикойтипа k и не являетсяграмматикой типа k+1.Ответ: k =_______4567№ группы_______8910(б) Каким из перечисленных классовпринадлежит язык L(G) ?Ответ:КлассL(G) ∈ ℑ?(да/нет)ℑконтекстно-свободные языкиконтекстно-зависимые языкирегулярные языкиязыки типа 0(в) Определение контекстно-зависимой грамматики.Ответ:2.

Для заданной КС-грамматики определить,является ли она:(а)приведенной (ответ обосновать);(б)однозначной (ответ обосновать).S → DSA | aB | abBC → bC | B | DD → Db | Ca| bB → aDC | b| εE → Ba | Bb3. Дана леволинейная(a) Построить по грамматике G1 конечный автомат A (соответствующийграмматика G1:алгоритму разбора) в виде диаграммы состояний. Показать, что автомат Aне является детерминированным.S → С⊥С → AbA → Ba | aB → Ab | Bb| Cb(б) По автомату A с помощью соответствующегоэквивалентный детерминированный автомат AD .алгоритма построить(в) По автомату AD построить эквивалентную леволинейную грамматику G24.

Имеется клетчатый лист бумаги, бесконечный вправо и вниз. В левом верхнем углу расположеноперо, оставляющее на бумаге след при перемещении. Перо управляется интерпретаторомграфопостроителем. На вход интерпретатору подается последовательность символов-команд изалфавита {a, b}:a — переместить перо на одну клетку вправо;b — переместить перо на одну клетку вниз.Например, по последовательностиabaaabbbaabb интерпретаторпостроит «лестницу», изображенную на рисунке.Построить грамматику с терминальным алфавитом {a,b},описывающую все лестницы, в которых не меньше одной ступени ивысота каждой ступени равна ширине. Пример такой лестницы — нарисунке.

В грамматике должно быть не более 5 правил вывода (считаяальтернативы). Ответ:5. (a) По процедурам анализатора, действующего методом рекурсивного спуска, восстановить КСграмматику.char c; void gc(){cin>>c;}; void S(); void A(); void B();int main(){ try{ gc();S(); if(c!=’\n’) throw c; cout<<”OK”<<endl; return 0;}catch(…) { cout<<”unexpected: ”<<c<<endl; return 1;}};void S(){if (c==’a’){ gc(); S();C();} else if()(c==’b’){ gc();} else throw c;}void C(){if (c==’c’){ gc();}void B(){if (c==’c’){ gc();C();}else if(c==’a’){ gc();B(); if(c==’a’) gc(); else throw c;} else throw c;}}(б) Удовлетворяет ли эта грамматика условиям, гарантирующим корректность работы данногоанализатора на любых входных цепочках ? Ответ обосновать.6.

Даны грамматики:S → aS | bSa | cAA → cA | εG1:G2:S → cEE → aE | baE | εВставить в G1 действия вида 〈cout << …〉 по переводу цепочек языка L1 =L(G1) в цепочки языкаL2 =L(G2), соблюдая следующее условие соответствия: цепочка x из L1 переводится методомрекурсивного спуска в цепочку y из L2 , такую что | x | a = | y | a , | x | b = | y | b , где | x | a означаетколичество вхождений символа a в x.Ответ:7. Дать определения и описать наиболее важные различия понятий «программа» и «программныйпродукт».8. Привести примеры основных преобразований машинно-независимой оптимизации программ.9.

Записать результат перевода в ПОЛИЗ (постфиксную запись) фрагмента программы на языке Си:for (; i < 9; i = i + 1) w = t < 0 ? –t : t + 6;Ответ :ПОЛИЗ181234567891011121314151617192021222324252627282930313233343510. Перечислить основные требования к составу стандартных библиотек языков программирования.Вариант 2_2008ФИО____________________________________________1231. Дана грамматика G:S → BcS → aScdaBccd → aCсcdaC → CaaC→a(a) Классификация:найти такое целое k, чтоG является грамматикойтипа k и не являетсяграмматикой типа k+1.Ответ: k =_______4567№ группы_______8910(б) Каким из перечисленных классовпринадлежит язык L(G) ?Ответ:КлассL(G) ∈ ℑ?(да/нет)ℑрегулярные языкиконтекстно-зависимые языкиконтекстно-свободные языкиязыки типа 0(в) Определение контекстно-свободной грамматики.Ответ:2. Для заданной КС-грамматики определить,является ли она:(а)приведенной (ответ обосновать);(б)однозначной (ответ обосновать).S → DSA | aB | BaC → CC | bC | Cb | DD → Db | Ca| bB → aDC | bE → Ba | Bb3.

Дана леволинейная(a) Построить по грамматике G1 конечный автомат A (соответствующийграмматика G1:алгоритму разбора) в виде диаграммы состояний. Показать, что автомат Aне является детерминированным.S → A⊥A → BaB → Cb | b | aC → Ba | Ca| Aa(б) По автомату A с помощью соответствующегоэквивалентный детерминированный автомат AD .алгоритма построить(в) По автомату AD построить эквивалентную леволинейную грамматику G24. Имеется клетчатый лист бумаги, бесконечный вправо и вверх. В левом нижнем углу расположеноперо, оставляющее на бумаге след при перемещении. Перо управляется интерпретаторомграфопостроителем.

На вход интерпретатору подается последовательность символов-команд изалфавита {a,d}:a — переместить перо на одну клетку вправо;d — переместить перо на одну клетку вверх.Например, по последовательностиddaadddaaada интерпретаторпостроит «лестницу», изображенную на рисунке.Построить грамматику с терминальным алфавитом {a,d},описывающую все лестницы, в которых не меньше одной ступени иширина каждой ступени равна высоте. Пример такой лестницы — нарисунке. В грамматике должно быть не более 5 правил вывода (считаяальтернативы). Ответ:5.

(a) По процедурам анализатора, действующего методом рекурсивного спуска, восстановить КСграмматику.char c; void gc(){cin>>c;}; void S(); void A(); void B();int main(){ try{ gc();S(); if(c!=’\n’) throw c; cout<<”OK”<<endl; return 0;}catch(…) { cout<<”unexpected: ”<<c<<endl; return 1;}};void S(){if (c==’b’){ gc(); S();B();} else if()(c==’a’){ gc();} else throw c;}void A(){if (c==’a’){ gc();}void B(){if (c==’a’){ gc();A();}else if(c==’с’){ gc();B(); if(c==’b’) gc(); else throw c;} else throw c;}}(б) Удовлетворяет ли эта грамматика условиям, гарантирующим корректность работы данногоанализатора на любых входных цепочках ? Ответ обосновать.6.

Даны грамматики:S → dS | bSd | hEE → ε | hEG1:G2:S → hBB → dB | bdB | εВставить в G1 действия вида 〈cout << …〉 по переводу цепочек языка L1 =L(G1) в цепочки языкаL2 =L(G2), соблюдая следующее условие соответствия: цепочка x из L1 переводится методомрекурсивного спуска в цепочку y из L2 , такую что | x | d = | y | d , | x | b = | y | b , где | x | d означаетколичество вхождений символа d в x.Ответ:7. Описать основные пути передачи управления и информации в последовательном и параллельномрежимах работы лексического и синтаксического анализаторов. Дать необходимые пояснения.8. Дать определения процессов верификации, тестирования, регрессивного тестирования и отладкипрограммного продукта.

Описать различия в целях и задачах этих процессов..9. Записать результат перевода в ПОЛИЗ (постфиксную запись) фрагмента программы на языке Си:while (w < n + 2) if (f >= 0) w = t < 0 ? –t : t + 6;Ответ :ПОЛИЗ181234567891011121314151617192021222324252627282930313233343510. Дать определение системы программирования и перечислить основные этапы разработкипрограммных продуктов в рамках систем программирования.Вариант 3_2008ФИО____________________________________________1231.

Дана грамматика G:S → BcS → SdB → CaC→ aC → bB(a) Классификация:найти такое целое k, чтоG является грамматикойтипа k и не являетсяграмматикой типа k+1.Ответ: k =_______456№ группы_______78910(б) Каким из перечисленных классовпринадлежит язык L(G) ?Ответ:КлассL(G) ∈ ℑ?(да/нет)ℑконтекстно-свободные языкиконтекстно-зависимые языкиязыки типа 0регулярные языки(в) Определение регулярной грамматики.Ответ:2. Для заданной КС-грамматики определить,является ли она:(а)приведенной (ответ обосновать);(б)однозначной (ответ обосновать).S → ADS | bF | FbC → CbC | bC | Cb | DD → Db | Ca| bСF → bDC | aE → Ba | Bb3.

Дана леволинейная (a) Построить по грамматике G конечный автомат A (соответствующий1грамматика G1:алгоритму разбора) в виде диаграммы состояний. Показать, что автомат Aнеявляется детерминированным.S → Bc | cB → CbC → Aa | bA → Cb | Ab| Bb(б) По автомату A с помощью соответствующегоэквивалентный детерминированный автомат AD .алгоритма построить(в) По автомату AD построить эквивалентную леволинейную грамматику G24.

Имеется клетчатый лист бумаги, бесконечный вправо и вверх. В левом нижнем углу расположеноперо, оставляющее на бумаге след при перемещении. Перо управляется интерпретаторомграфопостроителем. На вход интерпретатору подается последовательность символов-команд изалфавита {e, f}:e — переместить перо по диагонали вправо-вверх на одну клетку;f — переместить перо вправо-вниз.Например, по последовательности eeffefeeefff интерпретаторпостроит «горную цепь», изображенную на рисунке.

«Гора»образуется двумя равными соседними отрезками.Построить грамматику с терминальным алфавитом{e, f }, описывающую все горные цепи, в которых неменьше одной горы. В грамматике должно быть не более 5правил вывода (считая альтернативы). Ответ:5. (a) По процедурам анализатора, действующего методом рекурсивного спуска, восстановить КСграмматику.char c; void gc(){cin>>c;}; void S(); void A(); void B();int main(){ try{ gc();S(); if(c!=’\n’) throw c; cout<<”OK”<<endl; return 0;}catch(…) { cout<<”unexpected: ”<<c<<endl; return 1;}};void S(){if (c==’b’){ gc(); S();A();} else if()(c==’a’){ gc();} else throw c;}void B(){if (c==’b’){ gc();}void A(){if (c==’a’){ gc();B();}else if(c==’с’){ gc();A(); if(c==’b’) gc(); else throw c;} else throw c;}}(б) Удовлетворяет ли эта грамматика условиям, гарантирующим корректность работы данногоанализатора на любых входных цепочках ? Ответ обосновать.6.

Даны грамматики:S → qS | dSq | gLL → gL | εG1:G2:S → gCC →ε | qC | dqCВставить в G1 действия вида 〈cout << …〉 по переводу цепочек языка L1 =L(G1) в цепочки языкаL2 =L(G2), соблюдая следующее условие соответствия: цепочка x из L1 переводится методомрекурсивного спуска в цепочку y из L2 , такую что | x | q = | y | q , | x | d = | y | d , где | x | q означаетколичество вхождений символа q в x.Ответ:7. Привести примеры основных преобразований машинно-независимой оптимизации программ.8. Описать основные пути передачи управления и информации в последовательном и параллельномрежимах работы лексического и синтаксического анализаторов.

Дать необходимые пояснения..9. Записать результат перевода в ПОЛИЗ (постфиксную запись) фрагмента программы на языке Си:while (y < n + 2) if (s >= 3) if (n > 0) y = n + 2; else y = –n;Ответ :ПОЛИЗ181234567891011121314151617192021222324252627282930313233343510. Дать определение интегрированной среды разработки (ИСР), перечислить основные компонентыИСР..