Теория и реализация языков программирования



         

КС-грамматики и МП-автоматы


4.1.1. Пусть G - грамматика с правилами:

S

SbS|ScS|a

Найти 2 различных дерева вывода для цепочки abaca.

4.1.2. Дана однозначная КС-грамматика G = (N, T, P, S) и цепочка w

L(G). Количество элементов во множествах N, T, P равно n1, n2, n3 соответственно, а |w| = l. Найти нижнюю и верхнюю границу для числа деревьев разбора w в G.

4.1.3. Являются ли однозначными следующие грамматики?

а) S

a|C; C
AB; A
aA|Ba|a; B
aB; б) S
BA; A
Aa|bA|?; B
Bb|aB|b; в) S
b|C; C
aC|AC; A
aA|Aa|a; г) S
AB; A
aA|bA|a; B
Ba|Bb|?; д) S
A|B; A
AA|a; B
aB|b|C; C
cC; е) S
aA|bB; A
aA|a|b; B
bB|b|?; ж) S
aAc|bS; A
aA|Aa|?; з) S
aA|b; A
abA|abAcb; B
c; и) S
aB|cA; A
BaA|a; B
A|a; к) S
ABS|?; A
abA|a; B
Ba|Bab|?.

4.1.4. Является ли однозначной грамматика с правилами:

а) S

A|B; B
aB|b|C; A
AA|a; C
cC; б) S
aAc|bS; A
aA|Aa|c; в) S
aA|b; A
abA|abAcb; B
c; г) S
aB|cA; A
BaA|a; B
A|b; д) S
a|C; C
AB; A
aA|Ba|a; B
aB; е) S
BA; A
Aa|bA|?; B
Bb|aB|b; ж) S
b|C; C
aC|AC; A
aA|Aa|a; з) S
AB; A
aA|bA|a; B
Ba|Bb|?.

4.1.5. Пусть G1 - грамматика, имеющая продукции:

S

bA|ab; A
a|aS|bAA; B
b|bS|aBB;

а G2 - грамматика, определяемая продукциями:

S

aB|aBS|bAS|bA; A
bAA|a; B
bBB|b.

Показать, что

1) G1 - неоднозначная грамматика; 2) G2 - однозначная грамматика; 3) L(G1) = L(G2):

4.1.6. Какой язык допускается автоматом с магазинной памятью

P = (Хq0}, {a, b}, {z0},

, q0, z0, {q0}) ?

4.1.7. Построить МП-автоматы, определяющие языки

а) {wwR : w

{a, b}*}; б) язык всех цепочек из нулей и единиц с одинаковым числом тех и других в) {{a, b}* \ {ambnambn} : m, n
1}; г) {{a, b}* \ {ambnam} : m, n
1}; д) {{a, b}* \ {ww} : w
{a, b]*}:

4.1.8. Построить автомат с магазинной памятью, допускающий язык:

а) ({anbncm|n, m

1})
({ambncn|n, m
1}); б) {anckbn|k, n
1}; в) {ambncp|m + n + p
0(mod2), m, n, p
0}; г) {apbqcr|p + q > r; p, q, r
0}; д) {x|x
{a, b}*, |x|a = |x|b}; е) {x|x
{a, b}*, |x|a
|x|b}; ж) {x|x
{a, b}*; |x|a = |x|b, и для
u, v : x = uv; |u|
0, |v|
0 выполнено |u|a > |u|b}.

4.1.9. Пусть A - магазинный автомат.


Содержание  Назад  Вперед