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

UptoLike

ВУЗ: 

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

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

Рубрика: 

40
Положим M =({q
0
, q
1
, q
2
,..., q
n
, p}, {a
1
, a
2
,..., a
n
}, δ, q
0
, {q
n
}), где δ(q
i
, a
i +1
) =
q
i +1
,
δ(q
i
, a) = p, если a ≠ a
i +1
(i=0, 1,..., n –1), δ(q
n
, a)=δ(p, a) = p для всех a.
Очевидно, что fa M принимает только цепочку x.
Множество, содержащее только пустую цепочку, принимается конечным
автоматом M =({q
0
, p}, Σ, δ, q
0
, {q
0
}), где δ(q
0
, a) = δ( p, a) = p для всех a∈Σ.
Действительно, только пустая цепочка переводит автомат в состояние q
0
,
являющееся конечным.
Пустое множество принимается конечным автоматом M = ({q
0
}, Σ, δ, q
0
, ∅),
где δ(q
0
, a) = q
0
для всех a∈Σ.
Утверждение теоремы немедленно следует из свойства замкнутости языков
типа 3 относительно объединения. Что и требовалось доказать.
Определение 3.11. Произведением или конкатенацией языков L
1
и L
2
называется множество L
1
L
2
= {z | z = xy, x∈L
1
, y∈L
2
}. Другими словами, каждая
цепочка в языке L
1
L
2
есть конкатенация цепочки из L
1
с цепочкой из L
2
.
Например, если L
1
= {01, 11} и L
2
= {1, 0, 101}, то множество
L
1
L
2
= {011, 010, 01101, 111, 110, 11101}.
Теорема 3.9. Класс множеств, принимаемых конечными автоматами,
замкнут относительно произведения.
Доказательство. Пусть M
1
= (Q
1
, Σ
1
, δ
1
, q
1
, F
1
) и M
2
= (Q
2
, Σ
2
, δ
2
, q
2
, F
2
) —
детерминированные конечные автоматы, принимающие языки L
1
и L
2
соответственно.
Предположим, что Q
1
∩ Q
2
= ∅. Кроме того, без потери общности можно
предположить, что Σ
1
= Σ
2
= Σ (в противном случае мы могли бы добавить
“мёртвые” состояния в Q
1
и Q
2
, как при доказательстве леммы 3.2).
Мы построим ndfa M
3
, принимающий язык L
1
L
2
.
Положим M
3
= (Q
1
∪ Q
2
, Σ, δ
3
, q
1
, F), где
1) δ
3
(q, a)={δ
1
(q, a)} для любого q∈Q
1
\ F
1
,
2) δ
3
(q, a) = {δ
1
(q, a), δ
2
(q
2
, a)} для любого q∈F
1
,
3) δ
3
(q, a) = {δ
2
(q, a)} для любого q∈Q
2
.
Если ε∉L
2
, то F = F
2
, иначе F = F
1
∪ F
2
.
Правило 1 воспроизводит движения автомата M
1
до тех пор, пока он не
достигает какого-нибудь из его конечных состояний, приняв некоторую
(возможно пустую) начальную часть входной цепочки, принадлежащую языку
L
1
. Затем согласно правилу 2 он может продолжать повторять движения
автомата M
1
или перейти в режим воспроизведения движений автомата M
2
,
начиная с его начального состояния. В последнем случае все дальнейшие
движения благодаря правилу 3 повторяют движения автомата M
2
. Если fa M
2
принимает (возможно пустое) окончание входной цепочки, принадлежащее
языку L
2
, то и автомат M
3
принимает всю входную цепочку. Другими словами,
T(M
3
) = L
1
L
2
.
Определение 3.12. Замыкание языка L есть множество
Предполагается, что L
0
= {ε}, L
n
= L
n –1
L = LL
n –1
при n >0.
Пример 3.5. Если L = {01, 11}, то L
*
= {ε,01,11,0101,0111,1101,1111, ...}.
*
0
.
k
k
L
L
∞
=
=
∪

Страницы