ВУЗ:
Составители:
недостижимые символы (т.е. символы, не встречающиеся ни в одном
терминальном порождении). Можно, увеличив число правил вывода,
ускорить вывод цепочек языка. Можно, наконец, представить правила
вывода в некоторой стандартной форме. Возможны и другие преобразования
грамматик. Покажем в качестве примера возможность получения из
некоторой грамматики эквивалентной ей с ускоренным выводом цепочек.
Пример 3.3. Грамматика },,,{ RSVVG
ATn
=
, в которой },,{ cвaV
T
= ,
},{ ASV
A
= ,
)6(
)5(
)4(
)3(
)2(
)1(
:
aAS
cAS
авsваS
cS
вsвS
asaS
R
→
→
→
→
→
→
порождает тот же язык, что и грамматика G
m
, но некоторые
его цепочки порождаются за меньшее число шагов вывода. Например, слово
аавсваа выводится в G
n
за три шага: аавсваааавSвааaSaS
)3()4()1(
→→→ , в то время как
в G
m
оно выводится за четыре шага. Заметим попутно, что грамматику G
n
можно упростить, выбросив правила (5) и (6), так как они включают
непроизводящие нетерминальные символы А.
Пусть в некоторой грамматике G имеется вывод
yА
G
→ , где А -
нетерминальный символ, а y - произвольная цепочка. Очевидно, что не
изменяя язык, порождаемый этой грамматикой, можно добавить к ней
правило вывода вида
yA → . Говорят, что это правило, получено
сокращением вывода. Нетрудно видеть, что к грамматике G
n
таким правилом
является правило
авSваS → . Ясно, что в грамматику G
n
может быть
добавлено сколь угодно правил такого типа.
Грамматика, в которой существует более одного вывода хотя бы одной
терминальной цепочки, называется неоднозначной. Если некоторая цепочка
имеет р равных выводов в данной грамматике, то говорят, что степень ее
неоднозначности равна р. Язык, порождаемый неоднозначной грамматикой,
Страницы
- « первая
- ‹ предыдущая
- …
- 51
- 52
- 53
- 54
- 55
- …
- следующая ›
- последняя »
