Составители:
33
Пусть
q
’
∈ Q
’
и q
’
= δ
’
(q
0
’, x). Сопоставим с состоянием q
’
∈Q
’
состояние q ∈ Q,
достижимое автоматом
M по прочтении той же цепочки x: q = δ(q
0
, x) = δ([ε]
R
, x) = [x]
R
.
Это сопоставление является непротиворечивым.
Действительно, если
q
’
, p
’
∈Q
’
и q
’
= p
’
, причём q
’
= δ
’
(q
0
’, x), а p
’
= δ
’
(q
0
’, y), то
их образы есть соответственно
q = δ(q
0
, x) = δ([ε]
R
, x) = [x]
R
и p = δ(q
0
, y) =
δ([
ε]
R
, y) = [y]
R
. Учитывая, что x и y принадлежат одному и тому же классу экви-
валентности отношения
R
’
и что R
’
⊆ R, заключаем, что x и y также находятся в
одном и том же классе эквивалентности отношения R, т.е. [x]
R
= [y]
R
, и потому q
=
p. Другими словами, если прообразы состояний равны, то равны и их образы.
Кроме того, если fa M
’
совершает переход из состояния q
’
в состояние p
’
,
прочитав символ
a∈Σ, то fa M переходит из состояния q, являющегося образом
q
’
, в состояние p, являющееся образом p
’
, прочитав тот же самый символ a ∈Σ,
так как δ([
x]
R
, a) = [xa]
R
(см. рис. 3.4).
§ 3.3. Недетерминированные
конечные автоматы
Теперь мы введём понятие недетерминированного конечного автомата
(ndfa —
nondeterministic finite automaton). От своего детерминированного
аналога он отличается только типом управляющего отображения δ. Мы
увидим, что любое множество, принимаемое недетерминированным конечным
автоматом, может также приниматься детерминированным конечным
автоматом. Однако недетерминированный конечный автомат является
полезным понятием при доказательстве теорем. Кроме того, с этого
простейшего понятия легче начать знакомство с недетерминированными
устройствами, которые не эквивалентны своим детерминированным аналогам.
Определение 3.6. Недетерминированным конечным автоматом называет-
ся формальная система
M = (Q, Σ, δ, q
0
, F), где Q — конечное непустое мно-
жество
состояний, Σ — входной алфавит, δ — отображение типа Q × Σ → 2
Q
,
q
0
∈ Q — начальное состояние, F ⊆ Q — множество конечных состояний.
Существенная разница между детерминированной и недетерминированной
моделями конечного автомата состоит в том, что значение δ(
q, a) является
(возможно пустым) множеством состояний, а не одним состоянием.
Запись δ(
q, a) = {p
1
, p
2
,..., p
k
} означает, что недетерминированный конеч-
ный автомат
M в состоянии q, сканируя символ a на входной ленте, продвигает
входную головку вправо к следующей ячейке и выбирает любое из состояний
p
1
, p
2
,..., p
k
в качестве следующего.
M
’
:
q
’= δ
’
(q
0
’ , x)
M
:
q = δ([ε]
R
, x) = [x]
R
p = δ([
ε
]
R
, xa) = [xa]
R
p’= δ
’
(q’, a) = δ
’(
δ
’
(q
0
’ , x), a) = δ
’
(q
0
’ , xa)
x
x
a
Рис. 3.4.
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
