Стр. 43 - Информационные структуры и их преобразование
Упрощенная HTML-версия
41
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
F - множество заключительных символов:
Q F
⊂
.
Конфигурация автомата определяется символами (q, W, S), где
*
W , S
Σ∈ Γ∈
(цепочка входных символов).
Переход из одного состояния в другое - бинарная операция:
(q
0
,
α
W, Z)|- (q
1
, W,
α
Z).
Это имеет место тогда и только тогда, когда
)Z,q( )Z,W,q(
1
0
α = α δ
.
Цепочка принимается автоматом, если возможен переход:
),W,q(
0
α
|―
)e,e,q(
1
,
где
0
1
q, W,F q
Σ∈ ∈
- начальное состояние, е - пустая цепочка (
λ
).
Любая программа может быть записана в постфиксной форме.
Функция отображения:
*
F Q Г)Ue(Q
× → × Σ×
, где
Γ
- символ,
*
F
-
подмножество символов.
Автоматы могут не считывать ничего из входной цепочки, а работать
только с магазином. Если магазин пуст, то автомат считывает символ из
входной цепочки.
Язык:
)Z,q( )Z,aW,q(
1
0
= α
δ
. Верхний символ магазина - левый символ
цепочки - загружаем в магазин и сравниваем. Если цепочка считана и в
магазине - маркер дна, то цепочка принята автоматом.
I.
}1 n/10{ L
nn
≥
=
=
2
1
0
q
q
q
Q
0
q
- загрузка,
1
q
- сравнение,
2
q
- заключительное состояние (цепочка
принята или нет).
}Z,1,0{ Г},1,0{
=
=Σ
,
δ
- не знаем;
0
q
- начальное состояние;
Z- начальные символы магазина; МП=
{
}
2
0
2 1 0
q,Z,q,),Z,1,0(),1,0(),q,q,q(
δ
;
2
q
- заключительное состояние.
Функция отображения:
Автомат детерминированный.
1)
)Z0,q( )Z,0,q(
0
0
=
δ
- 0 в магазин;
2)
)Z00,q( )Z0,0,q(
0
0
=
δ
- загрузка магазина;
3)
)Z,q()Z0,1,q(
1
0
=
δ
- сравнение 1 и 0;
4)
)e,q( )Z,e,q(
2
1
=
δ
- убираем маркер.
Рассмотрим 0011:
