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



         

Грамматики


2.3.1. Принадлежит ли цепочка x = abaababb языку, порождаемому грамматикой с правилами:

S

SaSb|?

2.3.2. Принадлежит ли цепочка x = (()())() языку, порождаемому грамматикой с правилами:

S

SA|A A
(S)|()

2.3.3. Принадлежит ли цепочка x = 00011011 языку, порождаемому грамматикой с правилами:

S

SS|A A
0A1|S|01

2.3.4. Принадлежит ли цепочка x = 0111000 языку, порождаемому грамматикой с правилами:

S

A0B|B1A A
BB|0 B
AA|1

2.3.5. Верно ли соотношение a*cb* 2 L(G) для следующей грамматики G?

S

Bab|aDa; A
Dc|cA; B
Sb|b; D
AB|aD.

2.3.6. Верно ли соотношение ab*c* 2 L(G) для следующей грамматики G?

S

SAS|A; A
Ac|Da|b; B
DaD; D
ABD|AB.

2.3.7. Верно ли соотношение ca*b* 2 L(G) для следующей грамматики G?

S

bcD|aB; A
Db|cA; B
bS|?; D
BA|cD.

2.3.8. Верно ли соотношение c*ab* 2 L(G) для следующей грамматики G?

S

ASS|A; A
c|Ab|aD; B
aDD; D
AB|BaB.

2.3.9. Пусть грамматика G определяется правилами

S

AB; AB
CBb; CB
ABB; A
a; aB
a:

Какому классу (по Хомскому) она принадлежит? Порождается ли L(G) грамматикой более узкого класса?

2.3.10. Пусть грамматика G определяется правилами

S

aAbB; AbB
aAbB; bBb
bb; A
?.

Какому классу (по Хомскому) она принадлежит? Порождается ли L(G) грамматикой более узкого класса?

2.3.11. Пусть грамматика G определяется правилами

S

AaB; AaB
aAaBb; aBb
abb; A
?.

Какому классу (по Хомскому) она принадлежит? Порождается ли L(G) грамматикой более узкого класса?

2.3.12. Пусть грамматика G определяется правилами

S

AB; AB
aDB; DB
ABB; B
b; Ab
b.

Какому классу (по Хомскому) она принадлежит? Порождается ли L(G) грамматикой более узкого класса?

2.3.13. Какому классу по Хомскому принадлежит:

а) Грамматика с правилами:

S

AS|?; A
a|b:

б) Язык, порождаемый этой грамматикой?

2.3.14. Какому классу по Хомскому принадлежит:

а) Грамматика с правилами:

S

AB; AB
aABB; B
b; A
a;

б) Язык, порожденный этой грамматикой?

2.3.15. Какому классу по Хомскому принадлежит:

а) Грамматика с правилами:

S

ASB|BSA; A
a; B
b|?; SB
?;

б) Язык, порожденный этой грамматикой?

2.3.16.


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