ВУЗ:
Составители:
A → aAb | ab;
В → АА | A | a.
4.5.3. Построение грамматики с продуктивными нетерминалами
Нетерминальный символ А называется непродуктивным (непроизводящим), если он не
порождает ни одной терминальной цепочки, т.е. не существует вывода А →
*
х, где х∈V
*
T
.
Поэтому представляет интерес удаление из грамматики всех непродуктивных
нетерминальных символов. Рассмотрим, как для произвольной КС-грамматики можно
построить эквивалентную КС-грамматику, все нетерминальные символы которой
продуктивны. С этой целью выделяется множество W
1
={A | A → ϕ ∈ P, ϕ ∈ V
*
T
}. Затем
строится множество W
1
, W
2
, . . . , W
n+1
по следующим правилам:
W
n+1
= W
n
∪{BB → x ∈ P, x ∈ (V
T
∪ W
n
)
*
}.
Пусть задана грамматика G со следующими правилами вывода: S → SA | BSb | bAb; A →
aSa | bb; B → bBb | BaA. Построим множество продуктивных нетерминалов:
W
1
= {A}, т.к. в множестве P есть правило A → bb;
W
2
= {A, S}, т.к. имеется правило S → bAb и A ∈ W
1
;
W
3
= W
2
.
Все символы множества V
N
\W
n
являются непродуктивными, не используются в выводе
никакой терминальной цепочки и их можно удалить из грамматики вместе со всеми
правилами, в которые они входят. Грамматика G
1
, эквивалентная исходной грамматике,
будет включать следующее множество правил:
S → SA | bAb; A → aSa | bb.
В грамматике G
1
все нетерминалы продуктивны.
4.5.4. Построение грамматики, аксиома которой зависит от всех нетерминалов
Существует еще один тип нетерминальных символов, которые можно удалять из
грамматики вместе с правилами, в которые они входят. Например, в грамматике G, заданной
множеством правил P: S → aSb | ba; A → aAa | bba, нетерминал А не участвует ни в каком
выводе, т.к. из аксиомы нельзя вывести цепочку, содержащую этот нетерминал. Поэтому из
заданной грамматики можно удалить нетерминал А. Рассмотрим, как для произвольной КС-
грамматики можно построить эквивалентную КС-грамматику, аксиома которой зависит от
всех нетерминальных символов.
Для этого построим множество нетерминалов, от которых зависит аксиома. С этой
целью выделим множества W
1
, W
2
, . . . , W
n+1
по следующим правилам:
W
1
= {S},
W
n+1
= W
n
∪{B | A → xBy ∈ P, A ∈ W
n
}.
Нетерминал B∈W
n
тогда и только тогда, когда аксиома S зависит от B. Все нетерминалы,
не содержащиеся в W
n
, можно удалить из грамматики вместе с правилами, в которые они
входят.
Пример. Пусть дана КС-грамматика G:
S → abS | ASa | ab; A → abAa | ab; B → bAab | bB.
Найдем нетерминалы, от которых зависит аксиома:
W
1
= {S},
W
2
= {S, A}, т.к. имеется правило S → Asa и S ∈ W
1
;
W
3
= W
2
.
Эквивалентная грамматика G
1
, аксиома которой зависит от всех нетерминальных
символов:
S → abS | ASa | ab; A → abAa | ab.
A → aAb | ab; В → АА | A | a. 4.5.3. Построение грамматики с продуктивными нетерминалами Нетерминальный символ А называется непродуктивным (непроизводящим), если он не порождает ни одной терминальной цепочки, т.е. не существует вывода А →* х, где х∈V*T. Поэтому представляет интерес удаление из грамматики всех непродуктивных нетерминальных символов. Рассмотрим, как для произвольной КС-грамматики можно построить эквивалентную КС-грамматику, все нетерминальные символы которой продуктивны. С этой целью выделяется множество W1={A | A → ϕ ∈ P, ϕ ∈ V*T}. Затем строится множество W1, W2, . . . , Wn+1 по следующим правилам: Wn+1 = Wn ∪{BB → x ∈ P, x ∈ (VT ∪ Wn)*}. Пусть задана грамматика G со следующими правилами вывода: S → SA | BSb | bAb; A → aSa | bb; B → bBb | BaA. Построим множество продуктивных нетерминалов: W1 = {A}, т.к. в множестве P есть правило A → bb; W2 = {A, S}, т.к. имеется правило S → bAb и A ∈ W1; W3 = W2. Все символы множества VN\Wn являются непродуктивными, не используются в выводе никакой терминальной цепочки и их можно удалить из грамматики вместе со всеми правилами, в которые они входят. Грамматика G1, эквивалентная исходной грамматике, будет включать следующее множество правил: S → SA | bAb; A → aSa | bb. В грамматике G1 все нетерминалы продуктивны. 4.5.4. Построение грамматики, аксиома которой зависит от всех нетерминалов Существует еще один тип нетерминальных символов, которые можно удалять из грамматики вместе с правилами, в которые они входят. Например, в грамматике G, заданной множеством правил P: S → aSb | ba; A → aAa | bba, нетерминал А не участвует ни в каком выводе, т.к. из аксиомы нельзя вывести цепочку, содержащую этот нетерминал. Поэтому из заданной грамматики можно удалить нетерминал А. Рассмотрим, как для произвольной КС- грамматики можно построить эквивалентную КС-грамматику, аксиома которой зависит от всех нетерминальных символов. Для этого построим множество нетерминалов, от которых зависит аксиома. С этой целью выделим множества W1, W2, . . . , Wn+1 по следующим правилам: W1 = {S}, Wn+1 = Wn ∪{B | A → xBy ∈ P, A ∈ Wn}. Нетерминал B∈Wn тогда и только тогда, когда аксиома S зависит от B. Все нетерминалы, не содержащиеся в Wn, можно удалить из грамматики вместе с правилами, в которые они входят. Пример. Пусть дана КС-грамматика G: S → abS | ASa | ab; A → abAa | ab; B → bAab | bB. Найдем нетерминалы, от которых зависит аксиома: W1 = {S}, W2 = {S, A}, т.к. имеется правило S → Asa и S ∈ W1; W3 = W2. Эквивалентная грамматика G1, аксиома которой зависит от всех нетерминальных символов: S → abS | ASa | ab; A → abAa | ab.
Страницы
- « первая
- ‹ предыдущая
- …
- 30
- 31
- 32
- 33
- 34
- …
- следующая ›
- последняя »