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

UptoLike

ВУЗ: 

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

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

Рубрика: 

34
Область определения δ может быть расширена на Q × Σ
*
следующим образом:
Область определения δ может быть расширена далее до 2
Q
×Σ
*
следующим
образом:
δ({
p
1
, p
2
,..., p
k
}, x) =
Определение 3.7. Цепочка x∈ Σ
*
принимается недетерминированным коне-
ным автоматом M, если существует состояние p, такое, что p ∈F и p∈δ(q
0
, x).
Множество всех цепочек
x, принимаемых ndfa M, обозначается T(M).
Замечание 3.2. Напомним, что 2
Q
, где Q — любое множество, обозначает
степенное множество или множество всех подмножеств Q.
Пример 3.2. Рассмотрим недетерминированный конечный автомат, кото-
рый распознает множество {0,1}
*
{00,11}{0,1}
*
:
M = ({q
0
, q
1
, q
2
, q
3
, q
4
}, {0, 1}, δ, q
0
, {q
2
, q
4
}), где
δ(
q
0
,0)={q
0
, q
3
}, δ(q
0
,1)={q
0
, q
1
}, δ(q
1
,0)=∅, δ(q
1
,1)={q
2
}, δ(q
2
,0)={q
2
},
δ(
q
2
,1)={q
2
}, δ(q
3
,0)={q
4
}, δ(q
3
,1) = ∅, δ(q
4
,0)={q
4
}, δ(q
4
,1)={q
4
}.
На
рис. 3.5 приведена диаграмма состояний этого автомата. Фактически он
принимает любые цепочки, составленные из нулей и единиц, в которых
встречаются два подряд идущих нуля или единицы.
Теорема 3.4. Пусть L — множество, принимаемое недетерминированным
конечным автоматом. Тогда существует детерминированный конечный
автомат
, который принимает L.
Доказательство. Пусть
M = (Q, Σ, δ, q
0
, F) — ndfa и L = T(M). Определим
dfa
M
’
= (Q
’
, Σ
’
, δ
’
, q
0
’, F
’
) следующим образом. Положим Q
’
={[s] | s ∈2
Q
}.
Состояние
из множества Q
’
будем представлять в виде [q
1
, q
2
, ... , q
i
], где q
1
, q
2
, ... ,
q
i
— состояния из множества Q. Будем использовать обозначение ϕ для случая
i =0 или, что то же самое, s = ∅. Начальное состояние q
0
’ = [q
0
].
Таким образом, dfa
M
’
будет хранить след всех состояний, в которых ndfa
M мог бы быть в любой данный момент. Пусть F
’
— множество всех
состояний из
Q
’
, содержащих хотя бы одно состояние из множества конечных
состояний
F. Входной алфавит Σ — такой же, как в данном ndfa M.
для каждого x ∈ Σ
*
и a∈Σ.
0
0
0, 1
q
2
0, 1
1
q
1
0, 1
q
0
q
3
1
q
4
(, )
(, ) = {}, (, ) = (, )
pqx
qqqxa pa
∈δ
δε δ δ
∪
,
1
().
k
i
i
p
x
=
δ
∪
Рис. 3.5.

Страницы