Составители:
129
c к правому концу слов так, чтобы выводы в G
2
могли происходить, как в
грамматике G
1
.
Теперь рассмотрим подстановку f (a)={a} для a∈V
T
и f (c)={ε}. Тогда
f (L(G
2
)) = L(G
1
) и, следовательно, подстановка не сохраняет класс csl.
Очень часто интерес представляют подстановки специальных типов.
Определение 9.3. Подстановка f называется конечной, если f(a) есть конеч-
ное множество для всех a из области определения f. Если f (a) — единственная
строка, то f — гомоморфизм.
Конечная подстановка и гомоморфизм являются специальными классами
подстановок. Из этого мы имеем следующие следствия:
Следствие 9.1. Классы регулярных, контекстно-свободных и языков типа 0
замкнуты относительно конечной подстановки и гомоморфизма.
Доказательство очевидно из теоремы 9.7.
Следствие 9.2. Класс контекстно-зависимых языков замкнут относительно
ε-свободной конечной подстановки и ε-свободного гомоморфизма.
Доказательство очевидно из теоремы 9.8.
Следствие 9.3. Класс контекстно-зависимых языков не замкнут относи-
тельно конечной подстановки и гомоморфизма.
Доказательство. Подстановка, использованная при доказательстве
теоремы 9.9, является гомоморфизмом.
Мы докажем ещё один результат, касающийся подстановок, поскольку он
необходим для последующей теоремы.
Определение 9.4. Класс языков замкнут относительно k-ограниченного
стирания, если для любого языка L этого класса и любого гомоморфизма h,
обладающего тем свойством, что h никогда не отображает более, чем k
последовательных символов любого предложения из языка L в ε, h(L)
находится в этом же классе.
Покажем, что класс контекстно-зависимых языков замкнут относительно
k-ограниченного стирания. Фактически справедливо более общее утверждение.
Пусть L ⊆ Σ
*
— контекстно-зависимый язык и пусть f(a) для любого a ∈ Σ тоже
контекстно-зависим. Тогда язык f (L) контекстно-зависим при условии, что
существует k >0, такое, что для x∈L и y ∈ f (x) выполняется неравенство
|y|≥k|x|.
Лемма 9.2. Класс контекстно-зависимых языков замкнут относительно
k-ограниченного стирания.
Доказательство. Пусть G
1
= ( , , P
1
, S
1
) — контекстно-зависимая грам-
матика. Без потери общности предположим, что правила, за возможным исклю-
чением
S
1
→ε, имеют вид α→β или A → a, где а
Пусть h — гомоморфизм со свойством, что h никогда не отображает более,
чем k последовательных символов любого предложения x∈L(G
1
) в ε.
Пусть целое l больше, чем k + 1, и больше длины самой длинной левой
части любого правила.
(1)
N
V
(1)
T
V
(1)
T
.
aV∈
(1)
(1)
N
N
, ,
,
A
V
V
+
∈α
β∈
Страницы
- « первая
- ‹ предыдущая
- …
- 128
- 129
- 130
- 131
- 132
- …
- следующая ›
- последняя »
