Стр. 48 - Информационные структуры и их преобразование
Упрощенная HTML-версия
46
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
∗
∗
Γ× →Γ× ∪ ×
Q
)e E(Q
,
∗
Γ
- множество символов.
(
)
(
)
∗
Γ∈γβ
γ
= β
δ
,
z,q z,a,q
1
0
.
Если известно количество начальных символов, то можно, считав
половину, установить маркер (е – такт).
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
Sz,q
bSbz ,e,q
bSbz ,q
Sbz ,b,q
Swz ,e,q wz,e,q
z,q
Sz,q
bSbz ,e,q
bSba ,q
Sbaz ,e,q
1
0
0
0
0
0
2
1
1
1
1
=
δ
=
δ
=
δ
δ
→
е - такт из входной цепочки символов не
считывает.
Автомат заносит некоторую часть цепочки (1/2), затем верхним
символом становится некоторый маркер – S, указывающий положение
середины цепочки. Далее помещаем очередной входной символ в магазин и
осуществляем замену по правилу:
S
bSb / aSa
→
.
Эквивалентность МП-автоматов и КС-грамматик
Нужно показать, что МП-автомат построен именно для КС-грамматик
(контекстно-свободных). Пусть мы имеем КС-грамматику:
{
}
S,p,,NG
Σ
и пусть в этой грамматике есть правило
(
)
+
Σ∪ ∈α ∈ α=
N ;N A; A
.
Построить автомат, который определяет язык
{ }
GL
, генерируемый
данной грамматикой:
{
}
{
}
Σ∪ =Γ
δΓΣ =
N
q,z,q,,,,Q K
2 0 0
1.
(
)
(
)
α =
δ
,q A,e,q
0
0
.
2.
(
)
(
)
e,q a,a,q
1
1
=
δ
.
−
−
−
=
состояное
ьное
заключител
q
сравнение
q
магазина
загрузка
q
Q
2
1
0
;a aa W ;a aa A
n 21
n 21
i
=
=
3.
(
)
(
)
(
)
N S
грамматики
символ
начальный
- S
e,q S,e,q
2
1
∈
.
(
)
(
)
(
)
(
)
(
)
e,q
Z,e,q
Za,,a,a,a,,a,a,q
Za,,a,a,a,,a,a,q
AZ,a,,a,a,q
2
правилу
III по
1
правилу
II по
n
2 1 n
2 1 1
n
2 1 n
2 1 0
правилу
I по
n
2 1 0
