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

UptoLike

ВУЗ: 

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

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

Рубрика: 

124
Рассмотрим
две грамматики G
1
= ( , ,P
1
, S
1
) и G
2
= ( , , P
2
, S
2
),
причём
обе либо контекстно-свободные, либо контекстно-зависимые, либо типа
0. Без потери общности можно предполагать, что
Кроме того, согласно лемме 9.1 и теореме 4.5 можно считать, что правила
грамматик G
1
и G
2
имеют форму α→β и A → a, где α и β — цепочки,
состоящие из одних только нетерминалов, A — одиночный нетерминал, а a —
одиночный терминальный символ. Кроме того, если G
1
и G
2
— контекстно-
свободные грамматики, то β = ε подразумевает, что α есть S
1
или S
2
и что α
никогда не появляется в правой части никакого правила.
Объединение.
Пусть где а множе-
ство P
3
содержит правила S
3
→ S
1
,
S
3
→ S
2
и все правила из множеств P
1
и P
2
за
исключением S
1
→ε и
S
2
→ε, если G
1
и G
2
— контекстно-зависимы. В случае,
когда G
1
и G
2
— контекстно-зависимы и S
1
→ε∈P
1
или S
2
→ε∈P
2
, добавим
правило S
3
→ε к множеству правил P
3
. Теперь грамматика G
3
— того же типа,
что и грамматики G
1
, G
2
,
и L(G
3
)=L(G
1
) ∪ L(G
2
).
Конкатенация.
Пусть где а множе-
ство P
4
содержит правило S
4
→ S
1
S
2
и все правила из множеств P
1
и P
2
, за
исключением правил S
1
→ε и
S
2
→ε, если G
1
и G
2
— контекстно-зависимы.
В случае, когда G
1
и G
2
— контекстно-зависимы и S
1
→ε∈P
1
, к множеству
правил P
4
добавим правило S
4
→ S
2
; если S
2
→ε∈P
2
,
то
добавим правило
S
4
→ S
1
. Если S
1
→ε∈P
1
и S
2
→ε∈P
2
, то
к множеству P
4
добавим правило
S
4
→ε. Теперь грамматика G
4
— того же типа, что и грамматики G
1
, G
2
и
L(G
4
)=L(G
1
) L(G
2
).
Рис. 9.1.
Заметим, что поскольку
и все правила из множеств P
1
, P
2
имеют
нетерминалы исключительно слева, невозможно, чтобы строка, образованная
правым концом сентенциальной формы грамматики G
1
, за которой следует
левый конец сентенциальной формы грамматики G
2
, могла быть левой
стороной правила в множестве P
4
. Это означает, что левая часть любого
правила целиком состоит из нетерминалов только одной из двух грамматик
(см. рис. 9.1). Соответственно и всё правило относится к одной исходной
грамматике. Доказательство того, что L(G
4
) = L(G
1
) L(G
2
) просто.
Замыкание.
Пусть где
P
5
= P
1
∪ {S
5
→ S
1
S
5
, S
5
→ ε} — в случае cfg G
1
. Иначе, когда G
1
— csg,
(1)
T
V
(2)
T
V
(1)
N
V
(2)
N
V
(1) (2)
NN
.
VV
∩
=∅
(1) (2) (1) (2)
3N N 3T T33
({},,,),GV V SV VPS=∪∪ ∪
(1) (2)
3N N
,SV V∉∪
(1)(2) (1)(2)
4N N 4T T44
({},,,),GV V SV VPS=∪∪ ∪
(1) (2)
4N N
,SV V∉∪
S
4
→
α → β
S
1
S
2
(1) (2)
NN
VV∪=∅
(1)
5NT55
(, ,,),GVVPS=
(1)
NN 55
{,},VV SS=∪
'
(1)
515 51515 51515 T
{,}{, }.P P S S S S S S aS aS aS aS S a V=∪ →ε, → → ∪ → → ∈
'
'
''

Страницы