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

UptoLike

ВУЗ: 

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

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

Рубрика: 

35
Определим δ
’
([q
1
, q
2
,..., q
i
], a) = [p
1
, p
2
, ..., p
j
] тогда и только тогда, когда
δ({
q
1
, q
2
,..., q
i
}, a) = {p
1
, p
2
,..., p
j
}.
Индукцией по длине
l входной цепочки x∈ Σ
*
легко показать, что δ
’
(q
0
’, x) =
[
q
1
, q
2
,..., q
i
] тогда и только тогда, когда δ(q
0
, x) = {q
1
, q
2
,..., q
i
}.
База. Пусть
l = 0. Утверждение выполняется, ибо δ
’
(q
0
’, ε) = q
0
’ = [q
0
] и
δ(
q
0
, ε) = {q
0
}.
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех
l ≤ n (n ≥ 0).
Индукционный переход. Докажем, что тогда утверждение выполняется
и для
l = n +1.
Пусть
x = za, где z∈Σ
*
, |z| = n, a ∈ Σ. Тогда δ
’
(q
0
’, x) = δ
’
(q
0
’, za) = δ
’
(δ
’
(q
0
’, z), a).
По
индукционному предположению δ
’
(q
0
’, z)=[p
1
, p
2
,..., p
j
] тогда и только тогда,
когда δ(
q
0
, z) = {p
1
, p
2
, ... , p
j
}. В то же время по построению δ
’
([p
1
, p
2
, ... , p
j
], a)=
=[
q
1
, q
2
,..., q
i
] тогда и только тогда, когда δ({p
1
, p
2
,..., p
j
}, a) = {q
1
, q
2
,..., q
i
}.
Таким образом, δ
’
(q
0
’, x)=δ
’
(q
0
’, za)=δ
’
([p
1
, p
2
,..., p
j
], a)= [q
1
, q
2
,..., q
i
] тогда и
только тогда, когда δ(
q
0
, x) = δ(q
0
, za) = δ({p
1
, p
2
,..., p
j
}, a) = {q
1
, q
2
,..., q
i
}.
Чтобы закончить доказательство, остаётся добавить, что δ
’
(q
0
’, x) ∈ F’ точно
тогда, когда δ(
q
0
, x) содержит состояние из множества конечных состояний F.
Следовательно,
T(M) = T(M
’
). Что и требовалось доказать.
Поскольку детерминированные (dfa) и недетерминированные (ndfa)
конечные автоматы распознают одни и те же множества, мы будем называть их
общим термином
конечные автоматы (fa) в тех случаях, когда это различие не
существенно.
Пример 3.3. Пусть M = ({q
0
, q
1
}, {0, 1}, δ, q
0
, {q
1
}) — ndfa, где δ(q
0
, 0) =
{
q
0
, q
1
}, δ(q
0
, 1) = {q
1
}, δ(q
1
, 0) = ∅, δ(q
1
, 1) = {q
0
, q
1
}.
Построим детерминированный конечный автомат, эквивалентный данному.
Положим
M
’
= (Q
’
, {0, 1}, δ
’
, q
0
’, F
’
). Согласно теореме 3.4 в качестве состояний
детерминированного автомата следует взять все подмножества множества {
q
0
, q
1
},
включая пустое, т.е.
Q
’
= {ϕ, [q
0
], [q
1
], [q
0
, q
1
]}, причём q
0
’ = [q
0
].
Конечные состояния автомата
M
’
представлены теми подмножествами,
которые содержат конечные состояния данного автомата (в нашем случае:
q
1
),
т.е.
F
’
= {[q
1
], [q
0
, q
1
]}.
Наконец, δ
’
([q
0
], 0) = [q
0
, q
1
], δ
’
([q
0
], 1) = [q
1
], δ
’
([q
1
], 0) = ϕ, δ
’
([q
1
], 1) = [q
0
, q
1
],
δ
’
([q
0
, q
1
], 0) = [q
0
, q
1
], δ
’
([q
0
, q
1
], 1) = [q
0
, q
1
], δ
’
(ϕ, 0) = ϕ, δ
’
(ϕ, 1) = ϕ.
Поясним, что δ
’
([q
0
, q
1
], 0) = [q
0
, q
1
], так как δ(q
0
, 0) = {q
0
, q
1
}, δ(q
1
, 0) = ∅, и
{q
0
, q
1
} ∪∅ = {q
0
, q
1
}.
Аналогично, δ
’
([q
0
, q
1
], 1) = [q
0
, q
1
], ибо δ(q
0
,1) = {q
1
}, δ(q
1
, 1) = {q
0
, q
1
} и
{
q
1
} ∪ {q
0
, q
1
} = {q
0
, q
1
}.

Страницы