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

UptoLike

ВУЗ: 

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

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

Рубрика: 

126
II. Теперь предположим, что x∈T(P
2
). Тогда существуют движения вида
([ p
i
, q
i
], a
i +1
…a
n
, γ
i
)
([ p
i +1
, q
i +1
],
a
i +2
…a
n
, γ
i +1
) для 0 ≤ i < n, причём γ
0
= Z
0
,
[ p
n
, q
n
] ∈ F
P
× F
A
. Тогда δ
A
(q
i
, a
i +1
)=q
i +1
для 0 ≤ i < n, причём q
n
∈F
A
.
Следовательно, x ∈ R. Аналогично (p
i
, a
i +1
…a
n
, γ
i
)
( p
i +1
, a
i +2
…a
n
, γ
i +1
) для
0 ≤ i < n и, как следствие, (p
0
, x, Z
0
)
(p
n
, ε, γ
n
). Поскольку p
n
∈F
P
, то x∈L.
Из рассуждений I и II следует T(P
2
)=L ∩ R, что и требовалось доказать.
Мы уже видели в гл. 3, что класс регулярных множеств замкнут
относительно пересечения и дополнения. В гл. 7 было показано, что класс
рекурсивно перечислимых множеств не замкнут относительно дополнения.
Таким образом, мы имеем:
Теорема 9.5. Класс языков типа 0 не замкнут относительно дополнения.
В настоящее время неизвестно, замкнут ли класс контекстно-зависимых
языков относительно дополнения. Однако как класс языков типа 0, так и класс
контекстно зависимых языков замкнуты относительно пересечения.
Доказательства для обоих классов аналогичны, и хотя концептуально
просты, утомительны в деталях. Поэтому эти доказательства будут только
намечены.
Теорема 9.6. Класс языков типа 0 и класс контекстно-зависимых языков
замкнуты относительно пересечения.
Доказательство. Пусть L
1
и L
2
— языки типа 0 (контекстно-зависимые
языки). Рассмотрим две одноленточные машины Тьюринга (два недетермини-
рованных линейно ограниченных автомата) M
1
и M
2
, принимающие языки L
1
и
L
2
соответственно. Легко построить машину Тьюринга (lba) M, имеющую одну
оперативную ленту с тремя дорожками. Первая дорожка содержит ввод.
Машина M моделирует машину M
1
, используя дорожку 2. Если машина M
1
достигает когда-либо принимающую конфигурацию, то машина M перемещает
головку своей ленты на левый конец и моделирует машину M
2
на дорожке 3.
Если машина M
2
доходит до принимающей конфигурации, то машина M
принимает.
§ 9.2. Замкнутость
относительно отображений
Теперь рассмотрим результаты отображений разных типов над языками.
Первый тип, который мы рассмотрим, — подстановка.
Определение 9.1. Подстановка f есть отображение конечного множества
Σ на подмножества ∆
*
некоторого конечного множества ∆. Другими словами,
подстановка f с каждым символом из множества Σ ассоциирует некоторый
язык. Отображение f может быть распространено на строки из Σ
*
следующим
образом:
f(ε)=ε, f(xa)=f(x) f(a), где x∈Σ
*
, a∈Σ.
Очевидно, что f(x) нужно понимать в обобщенном смысле, тогда как f(a) —
в первоначальном.
1
*
__
P
1
__
P
2
*
__
P

Страницы