tasks_2008 (1119739)
Текст из файла
Вариант 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. Дать определение интегрированной среды разработки (ИСР), перечислить основные компонентыИСР..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
