контрольная работа
Cрок выполнения : 25.02
Вид работы : Контрольная
Дисциплины:
Технические: Другое.
|
|
Добавлен 13.02.2013 18:42:13
Уникальность:
Доработка:
Подробно: Задачи по курсу «Основы трансляции». Кроме ответов на вопросы в учебном пособии (главы 1, 2, 3, 4, 7, 11), необходимо решить любые 25 задач из приведенных 38 ниже заданий. Решение приводить полностью, указывая при выводе цепочек какие правила применили. 1. Дана грамматика. Построить вывод заданной цепочки. a) S T | T+S | T-S b) S aSBC | abC T F | F_x_T CB BC F a | b bB bb Цепочка a-b_x_a+b bC bc cC cc Цепочка aaabbbccc 2. Построить все сентенциальные формы для грамматики с правилами: S A+B | B+A A a B b 3. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? a) S APA b) S aQb | P + | - Q cSc A a | b c) S 1B d) S A | SA | SB B B0 | 1 A a B b 4. Построить грамматику, порождающую язык : a) L = { an bm | n, m >= 1} b) L = { ccc | , , - любые цепочки из a и b} c) L = { a1 a2 ... an an ... a2 a1 | ai = 0 или 1, n >= 1} d) L = { an bm | n m ; n, m >= 0} e) L = { цепочки из 0 и 1 с неравным числом 0 и 1} f) L = { | {a,b}+} g) L = { | {0,1}+ и содержит равное количество 0 и 1, причем любая подцепочка, взятая с левого конца, содержит единиц не меньше, чем нулей}. h) L = { (a2m bm)n | m >= 1, n >= 0} i) L = { | n >= 1} j) L = { | n >= 1} k) L = { | n >= 1} 5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка? a) S a | Ba b) S Ab B Bb | b A Aa | ba c) S 0A1 | 01 d) S AB 0A 00A1 AB BA A 01 A a B b e) S A | B f) S 0A | 1S A aAb | 0 A 0A | 1B B aBbb | 1 B 0B | 1B | g) S 0S | S0 | D h) S 0A | 1S | D DD | 1A | A 1A | 0B A 0B | B 0S | 1B B 0A | 0 i) S SS | A j) S AB A a | bb A a | cA B bA k) S aBA | l) S Ab | c B bSA A Ba AA c B cS 6. Эквивалентны ли грамматики с правилами : а) S AB и S AS | SB | AB A a | Aa A a B b | Bb B b b) S aSL | aL и S aSBc | abc L Kc cB Bc cK Kc bB bb K b 7. Построить КС-грамматику, эквивалентную грамматике с правилами: а) S aAb b) S AB | ABS aA aaAb AB BA A BA AB A a B b 8. Построить регулярную грамматику, эквивалентную грамматике с правилами: а) S A | AS b) S A.A A a | bb A B | BA B 0 | 1 9. Доказать, что грамматика с правилами: S aSBC | abC CB BC bB bb bC bc cC cc порождает язык L = {an bn cn | n >= 1}. Для этого показать, что в данной грамматике 1) выводится любая цепочка вида an bn cn (n >= 1) и 2) не выводятся никакие другие цепочки. 10. Написать КС-грамматику для языка L, построить дерево вывода и левосторонний вывод для цепочки aabbbcccc. L = {a2n bm c2k | m=n+k, m>1}.
Кратко: 1. Дана грамматика. Построить вывод заданной цепочки. a) S T | T+S | T-S b) S aSBC | abC T F | F_x_T CB BC F a | b bB bb Цепочка a-b_x_a+b bC bc cC cc Цепочка aaabbbccc