Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 32 стр.

UptoLike

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

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
}.
Нетерминал BW
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.