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

UptoLike

ВУЗ: 

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

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

Рубрика: 

133
1) a
i
∈Σ;
2) x
i
∈∆
*
,
1 ≤ i ≤ m.
Существуют состояния q
0
, q
1
,…, q
m
, такие, что q
m
∈F и (q
i
, x
i
) ∈δ(q
i –1
, a
i
)
для
1 ≤ i ≤ m.
Заметим,
что цепочка x
i
может быть равна ε. Нетрудно показать путем
построения
конечного автомата, принимающего R, что R — регулярное
множество.
Теперь L
1
∩ R есть множество всех слов вида a
1
x
1
a
2
x
2
…a
m
x
m
, m ≥ 0, где
a
i
∈Σ, x
i
∈∆
*
, 1 ≤ i ≤ m, x
1
x
2
…x
m
∈L, S(a
1
a
2
…a
m
) содержит цепочку x
1
x
2
…x
m
, и
ни одна цепочка x
i
не длиннее, чем k, причём k — длина самой длинной
цепочки x, такой, что ( p, x)∈δ(q, a) для некоторых состояний p, q∈Q и a∈Σ.
Наконец, пусть h — гомоморфизм, который отображает символ a в a для
каждого a ∈Σ и символ b — в ε для каждого b∈∆. Тогда S
–1
(L)=h(L
1
∩ R)
находится в классе C, поскольку h никогда не отображает больше k
последовательных символов в ε.
Теорема 9.12. Классы регулярных, контекстно-свободных языков, контекстно-
зависимых и языков типа 0 замкнуты относительно обратных gsm-отображений.
Доказательство
следует непосредственно из леммы 9.4 и того факта, что
названные
классы замкнуты относительно ε-свободной подстановки, k–ограни-
ченного стирания, а также пересечения и объединения с регулярным множеством.
Теперь рассмотрим операцию деления.
Определение 9.8. Пусть L
1
и L
2
— любые два языка. Определим частное от
деления L
1
на L
2
как множество {x | для некоторой цепочки y ∈ L
2
, такой, чтобы
xy ∈ L
1
}.
Пример 9.4. Пусть L
1
={a
n
b
n
| n ≥ 1} и L
2
= b
*
. Тогда
L
1
/ L
2
={a
i
b
j
| i ≥ j, i ≥ 1}, а L
2
/ L
1
= ∅.
Лемма 9.5. Каждый класс языков, замкнутый относительно конечной
подстановки и пересечения с регулярным множеством, замкнут относи-
тельно деления на регулярное множество.
Доказательство. Пусть C — класс языков, замкнутый относительно
названных операций. Пусть L∈Σ
1
*
— язык из класса C и R ⊆Σ
1
*
— регулярное
множество. Пусть Σ
2
= {a
’
| a∈Σ
1
} и f — конечная подстановка f (a)={a, a
’
}.
Рассмотрим L
2
= Σ
2
*
R ∩ f(L). Пусть h — гомоморфизм, определяемый
следующим образом: h(a)=ε и h(a
’
)=a для всех a∈Σ
1
.
Теперь L / R = h(L
2
). Поскольку класс C замкнут относительно конечной
подстановки и пересечения с регулярным множеством, то L / R находится в
классе C.
Теорема 9.13. Классы регулярных, контекстно-свободных и языков типа 0
замкнуты относительно деления на регулярное множество.
Доказательство следует непосредственно из леммы 9.5.
На вопрос: замкнут ли класс контекстно-зависимых языков относительно
деления на регулярное множество, ответим — нет.

Страницы