Задачи по «Основы трансляции»

Задачи  по курсу «Основы  трансляции».

Кроме ответов на вопросы  в учебном пособии (главы 1, 2, 3, 4, 7, 11), необходимо решить любые 25 задач из приведенных 38 ниже заданий. Решение приводить полностью, указывая при выводе цепочек какие правила применили.  

1.  Дана грамматика. Построить вывод заданной цепочки.

 

          a) S ® T | T+S | T-S b) S ® aSBC | abC

                T ® F | F*T  CB ® BC

                F ® a | b  bB ® bb

                Цепочка   a-b*a+b  bC ® bc

                            cC ® cc

                            Цепочка   aaabbbccc

2. Построить все сентенциальные формы для грамматики с правилами:

 

                S ® A+B | B+A

                A ® a

                B ® b

    3. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?

          a) S ® APA b) S ® aQb | e

                P ® + | -  Q ® cSc

                A ® a | b 

          c) S ® 1B d) S ® A | SA | SB

                B ® B0 | 1  A ® a

                            B ® b

4. Построить грамматику, порождающую язык :

1. L = { aⁿ b^m | n, m >= 1}

2. L = { acbcgc | a, b, g - любые цепочки из a и b}
3. L = { a₁ a₂ ... a_n a_n ... a₂ a₁ | a_i = 0 или 1, n >= 1}
4. L = { aⁿ b^m | n ¹ m ; n, m >= 0}
5. L = { цепочки из 0 и 1 с неравным числом 0 и 1}
6. L = { aa | a Î {a,b}⁺}
7. L = { w | w Î {0,1}⁺ и содержит равное количество 0 и 1, причем любая подцепочка, взятая с левого конца, содержит единиц не меньше, чем нулей}.
8. L = { (a^2m b^m)ⁿ | m >= 1, n >= 0}
9. L = { ^ | n >= 1}
10. L = { | n >= 1}
11. 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 | e

                D ® DD | 1A | e  A ® 1A | 0B

                A ® 0B | e  B ® 0S | 1B

                B ® 0A | 0 

          i) S ® SS | A j) S ® AB^

                A ® a | bb  A ® a | cA

                            B ® bA 

          k) S ® aBA | e 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 ® e  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 = {aⁿ bⁿ cⁿ | n >= 1}. Для этого показать, что в данной грамматике

1. выводится любая цепочка вида aⁿ bⁿ cⁿ (n >= 1) и
2. не выводятся никакие другие цепочки.

 

    10. Написать КС-грамматику для языка L, построить дерево вывода и левосторонний вывод для цепочки aabbbcccc. 

                L = {a²ⁿ b^m c^2k | m=n+k, m>1}.