Языки и трансляции. Мартыненко Б.К. - 62 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

61
§ 4.5. Свойство самовставленности
Определение 4.5. Говорят, что контекстно-свободная грамматика G явля-
ется самовставленной, если существует нетерминал A, такой, что A
α
1
Aα
2
,
где α
1
,α
2
∈V
+
. Говорят также, что нетерминал A является самовставленным.
Заметим, что именно свойство самовставленности является причиной
появления цепочек вида uv
i
wx
i
y. Возможно, некоторые понимают, что это
свойство самовставленности отличает строго контекстно-свободные языки от
регулярных множеств. Но отметим и то, что просто из-за свойства
самовставленности грамматики порождаемый ею язык не обязан быть
регулярным.
Например,
грамматика G =({S}, {a, b}, P, S), где P ={S → aSa, S → aS,
S → bS, S → a, S → b}, порождает регулярное множество. Действительно,
L(G)={a, b}
+
.
В этом параграфе будет показано, что контекстно-свободная грамматика,
которая не является самовставленной, порождает регулярное множество.
Следовательно, контекстно-свободный язык не регулярен тогда и только тогда,
когда все его грамматики — самовставленные.
Теорема 4.10. Пусть G — несамовставленная контекстно-свободная
грамматика. Тогда L(G) — регулярное множество.
Доказательство. Нетрудно убедиться в том, что если исходная
грамматика не является самовставленной, то и эквивалентная ей грамматика в
нормальной форме — тоже несамовставленная. В частности, это так для
нормальной формы Грейбах. Поэтому, если G — несамовставленная
грамматика, то мы можем найти грамматику G
1
= (
1
N
,
V
V
T
, P
1
, S
1
) в нормальной
форме Грейбах, эквивалентную грамматике G, которая тоже будет несамо-
вставленной. Хотя это утверждение не вполне очевидно, его легко доказать.
Ясно, что применение подстановок, описанных в лемме 4.2 не вводит
самовставленности. Что касается преобразований по исключению левой
рекурсии, описанных в лемме 4.3, то следует доказать, что нетерминал Z
самовставлен, только если нетерминал A — самовставлен. Кроме того, по
теореме 4.2 терминальная цепочка может быть выведена из каждого
нетерминала.
Рассмотрим левосторонний вывод в грамматике G
1
некоторой сентенциаль-
ной формы xα, x∈V
T
+
, α∈
Если G
1
имеет m нетерминалов и l — длина самой
длинной правой части правил, то никакая сентенциальная форма не может
иметь больше, чем ml нетерминалов.
Чтобы убедиться в этом, предположим, что в некоторой сентенциальной
форме α левостороннего вывода появляется больше, чем ml нетерминалов. В
дереве вывода α рассмотрим путь от корня к крайнему левому листу,
помеченному нетерминалом (рис. 4.4).
Узлы одного уровня представляют
*
G
⇒
1
N
*
.
V

Страницы