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

UptoLike

ВУЗ: 

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

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

Рубрика: 

41
Теорема 3.10. Класс множеств, принимаемых конечными автоматами,
замкнут относительно замыкания.
Доказательство. Пусть M = (Q, Σ, δ, q
0
, F) — dfa и L = T(M). Построим
ndfa M
′
, который принимает язык L
*
. Положим M
′
=(Q ∪ {q
0
′}, Σ, δ′, q
0
′,
F ∪ {q
0
′}), где q
0
′∉Q — новое состояние, и
Предназначение нового начального состояния q
0
′ — принимать пустую
цепочку. Если q
0
∉F, мы не можем просто сделать q
0
конечным состоянием,
поскольку автомат M может снова прийти в состояние q
0
,
прочитав некоторую
непустую цепочку, не принадлежащую языку L.
Докажем теперь, что T(M
′
) = L
*
.
I. Предположим, что x∈L
*
. Тогда либо x = ε, либо x = x
1
x
2
... x
n
, где x
i
∈L
(i = 1, 2, ... , n). Очевидно, что автомат M
′
принимает ε. Ясно также, что из x
i
∈
L следует, что δ(q
0
, x
i
) ∈F. Таким образом, множества δ
′
(q
0
′, x
i
) и δ
′
(q
0
, x
i
) каждое
содержит состояние q
0
и некоторое состояние p (возможно p = q
0
) из множества F.
Следовательно, множество δ
′
(q
0
′, x) содержит некоторое состояние из F и
потому x∈T(M
′
).
II. Предположим теперь, что x = a
1
a
2
... a
n
∈T(M
′
). Тогда существует некото-
рая последовательность состояний q
1
, q
2
,..., q
m
, такая, что значение δ
′
(q
0
′, a
1
) со-
держит состояние q
1
, значение δ
′
(q
i
, a
i +1
) содержит состояние q
i +1
(i = 1, 2, ...,
m –1) и q
m
∈F. Таким образом, для каждого i имеем q
i +1
= q
0
и δ(q
i
, a
i +1
) ∈F,
либо δ(q
i
, a
i +1
) = q
i +1
. Поэтому x = x
1
x
2
... x
n
, так что δ
′
(q
0
, x
i
) ∈F для 1 ≤ i ≤ n. Это
означает, что x
i
∈L, а x∈L
*
. Что и требовалось доказать.
Теорема 3.11. (С. Клини). Класс множеств, принимаемых конечными
автоматами, является наименьшим классом, содержащим все конечные
множества, замкнутым относительно объединения, произведения и замыка-
ния.
Доказательство. Обозначим наименьший класс множеств, принимаемых
конечными автоматами, содержащий все конечные множества и замкнутый
относительно объединения, произведения и замыкания, через
M. То, что класс
множеств, принимаемых конечными автоматами, содержит класс
M, является
непосредственным следствием из леммы 3.1 и теорем 3.8–3.10. Остаётся
показать, что класс
M содержит класс множеств, принимаемых конечными
автоматами.
Пусть L
1
— множество, принимаемое некоторым конечным автоматом
M = ({q
1
, q
2
, ... , q
n
}, Σ, δ, q
1
, F). Пусть
k
ij
R
обозначает множество всех цепочек x,
таких, что δ(q
i
, x) = q
j
, причём, если y является непустым префиксом x, не
совпадающим с x, то δ(q
i
, y) = q
l
, где l ≤ k. Другими словами,
k
ij
R
есть
δ′(q
0
′, a) =
{δ(q
0
, a), q
0
}, если δ(q
0
, a)
∈
F,
{
δ
(
q
0
, a
)}
в п
р
отивном сл
у
чае;
δ′(q, a) =
{δ(q, a), q
0
}, если δ(q, a)
∈
F,
{δ(q, a)} в противном случае для всех q∈Q.

Страницы