Составители:
132
Теперь для L∈C имеем S(L)=h( f(L) ∩ R). Поскольку класс языков C
замкнут относительно конечной подстановки и пересечения с регулярным
множеством, то язык S(L) тоже находится в C. Заметим, что требуется
замкнутость относительно конечной подстановки, а не ε-свободной конечной
подстановки, поскольку в [q, a, x, p] цепочка x может быть равна ε, и в этом
случае h([q, a, x, p]) = ε.
Теорема 9.10. Классы регулярных, контекстно-свободных и языков типа 0
замкнуты относительно gsm-отображений.
Доказательство. Теорема является прямым следствием леммы 9.3 и
теорем 9.4, 9.6 и 9.7.
Отметим, что gsm-отображения не сохраняют контекстно-зависимых
языков, поскольку каждый гомоморфизм является gsm-отображением.
Определение 9.7. Говорят, что gsm-отображение ε-свободно, если (p, ε)∉ δ(q, a)
для любых q, p∈Q и a ∈Σ.
Хотя
контекстно-зависимые языки не замкнуты относительно произвольных
gsm-отображений, они замкнуты относительно ε-свободных gsm-отображений.
Теорема 9.11. Класс контекстно-зависимых языков замкнут относи-
тельно
ε
-свободных gsm-отображений.
Доказательство. В лемме 9.3 конечная подстановка может быть заменена
на ε-свободную конечную подстановку при условии, что gsm-отображение
ε-свободно. Таким образом, поскольку класс контекстно-зависимых языков
замкнут относительно ε-свободной конечной подстановки и пересечения с
регулярным множеством, то этот класс замкнут относительно ε-свободных
gsm-отображений.
Рассмотрим теперь обратные gsm-отображения. Как увидим, регулярные,
контекстно-свободные, контекстно-зависимые и языки типа 0 все замкнуты
относительно обратных gsm-отображений.
Лемма 9.4. Пусть C — класс языков, замкнутый относительно
ε
-свобод-
ной подстановки, k-ограниченного стирания и объединения и пересечения с
регулярными множествами. Тогда класс C замкнут относительно обратных
gsm-отображений.
Доказательство. Пусть L ⊆∆
*
есть язык в классе C, а S =(Q, Σ, ∆, δ, q
0
, F)
— обобщённая последовательная
машина. Мы предполагаем без потери
общности, что Σ∩∆= ∅. Определим подстановку f следующим образом:
f(b)=Σ
*
b для каждого b ∈∆. (Отметим, что замкнутость относительно
объединения и пересечения с регулярными множествами гарантирует
принадлежность всех регулярных множеств классу C и, следовательно,
Σ
*
b∈C.)
Пусть L
1
= f(L) ∪Σ
*
, если ε∈L, и L
1
= f(L) в противном случае. Тогда L
есть множество всех строк вида y
1
b
1
y
2
b
2
…y
r
b
r
, r ≥ 1, где b
i
∈∆, y
i
∈Σ
*
,
1 ≤ i ≤ r, b
1
b
2
…b
r
∈L, объединенное с Σ
*
, если ε∈L. Применим теперь лемму 9.3
к классам регулярных, контекстно-свободных и языков типа 0.
Пусть R — регулярное множество, состоящее из всех слов вида
a
1
x
1
a
2
x
2
… a
m
x
m
, m ≥ 0, таких, что
Страницы
- « первая
- ‹ предыдущая
- …
- 131
- 132
- 133
- 134
- 135
- …
- следующая ›
- последняя »
