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

         

Преобразования КС-грамматик


4.3.1. Указать множество бесполезных символов для грамматики:

S

A|B; B
aB|b|C; A
AA|a; C
cC:

4.3.2. Указать множество бесполезных символов в грамматике G = ({S, A, B, C}, {a, b, c}, P, S), где P состоит из

S

aSb|Abb|? B
AB A
aBCb|bAb C
a|c.

4.3.3. Указать множество бесполезных символов в грамматике G = ({S, A, B, C}, {a, b, c}, P, S), где P состоит из

S

A|B A
aB|bS|b B
AB|Ba C
AS|b.

4.3.4. Указать множество бесполезных символов в грамматике G=({S, A, B, C, D}, {a, b, c}, P, S}, где P состоит из

S

aBb|aCb A
Dc|cA B
aS|b C
AB|aD D
AB|cDa.

4.3.5. Указать множество бесполезных символов в грамматике G = ({S, A, B, C}, {0, 1, 2}, P, S), где P состоит из

S

SS|A A
0A1|C|0 B
0C|1 C
BC|CS.

4.3.6. Являются ли следующие грамматики приведeнными? Указать для каждой грамматики множества недостижимых, бесплодных и бесполезных символов:

а) S

a|C б) S
BA C
AB A
Aa|bA|? A
aA|Ba|a B
Bb|aB|b; B
aB;

в) S

b|C г) S
AB C
aC|AC A
aA|bA|a A
aA|Aa|a; B
Ba|Bb|?;

д) S

A|B е) S
aA|bB A
AA|a A
aA|a|b B
aB|b|C B
bB|b|?; C
cC;

ж) S

aAc|bS з) S
aA|b A
aA|Aa|?; A
abA|abAcb B
c;

и) S

aB|cA к) S
ABS|? A
BaA|a A
abA|a B
A|a; B
Ba|Bab|?.

4.3.7. Построить приведeнные грамматики, эквивалентные следующим грамматикам:

a) S

A|B A
C|D B
D|E C
S|a|? D
S|b E
S|c|?; б) S
AB A
Aa|bB B
a|Sb.

4.3.8. Построить ?-свободные КС-грамматики, эквивалентные следующим грамматикам:

1) S

AB 2) S
ABC A
C|ab A
BB|? C
c|? B
CC|? B
aAa; C
AA|b;

3) S

aSbS 4) S
AB S
bSaS|?; A
SA|BB|bB B
b|aA|?.

4.3.9. Доказать, что для каждой КС-грамматики существует эквивалентная ей приведенная КС-грамматика.

4.3.10. Привести алгоритм построения множества достижимых символов и доказать его правильность

4.3.11. Доказать, что для каждой КС-грамматики существует эквивалентная ей КС-грамматика, не являющаяся леворекурсивной



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







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий