Языки и трансляции. Мартыненко Б.К. - 28 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

27
I-2.8. Пусть G грамматика, все продукции которой имеют форму A → xB и
A → x, где A и B нетерминалы, а x строка терминалов. Докажите, что L(G)
может быть порождён регулярной грамматикой.
I-2.9. Построить cfg, порождающую язык
L = {w | w∈{a, b}
*
, где #
a
w = 2 #
b
w }.
I-2.10. Написать КС-грамматику, порождающую числа без знака языка
программирования Паскаль.
I-2.11. Написать автоматную грамматику, порождающую числа без знака
языка Паскаль.
I-2.12. Дана контекстно-свободная грамматика G = (V
N
, V
T
, P, S),
где
V
N
= {S, A, B}, V
T
={a, b},
P ={S → aB, S → bA, A → a, A → aS, A → bAA, B → b, B → bS, B → aBB}.
Какой язык она порождает?
I-2.13. Какой язык порождает cfg G = (V
N
, V
T
, P, S), где V
N
= {E}, V
T
= {
a, +,
*
},
P = {E → a, E → E + E, E → E
*
E}, S = E? Какие недостатки этой грамматики?
I-2.14. Построить cfg, порождающую выражения (например, арифметиче-
ские). Проверить, сохраняет ли построенная грамматика информацию о поряд-
ке их вычисления.
I-2.15. Построить cfg, порождающую выражения (например, арифметиче-
ские) без “лишних” скобок.
Пояснение. Скобки “лишние”, если их можно восстановить по приоритетам операций или
в соответствии с правилом: “вычислять выражения с операциями одинакового старшинства
слева направо”.
I-2.16. Дана неукорачивающая грамматика G = (V
N
, V
T
, P, S),
где
V
N
= {S, B, C}, V
T
= {a, b, c},
P = { (1) S → aSBC, (2) S → aBC, (3) CB → BC,
(4) aB → ab, (5) bB → bb, (6) bC → bc, (7) cC → cc}.
Построить НС-грамматику, эквивалентную данной.
I-2.17. Построить csg, порождающую язык
L = {w | w ∈{a, b, c}
*
, где #
a
w = #
b
w = #
c
w }.
I-2.18. Построить csg, порождающую язык L = {ww | w ∈{0, 1}
*
}, т. е. L —
все слова в {0, 1}
*
, длины которых чётны, и первые и последние половины
которых равны.

Страницы