Стр. 44 - Информационные структуры и их преобразование
Упрощенная HTML-версия
42
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
)Z, 0011 ,q(
0
|-
)Z0,011,q(
0
|-
)Z00,11,q(
0
|-
)Z0,1,q(
1
|-
)Z,e,q(
1
|-
)e,q(
2
.
Рассмотрим
nn
10
:
)Z,10,q(
nn
0
|- за n шагов |-
)Z0,1,q(
n n
0
|-
)Z 0, 1,q(
1n1n
1
− −
|- за (n-1) шаг |-
)Z,e,q(
1
|-
)e,e,q(
2
.
Автомат может продолжить работу далее, если он прочёл всю входную
цепочку, но не сделает следующего шага, так как магазин пуст.
II.
{
}
)b,a( W/ WW L
r
∈
=
;
ba
W ab W
r
= ⇒ =
(обращение);
=
2
1
0
q
q
q
Q
;
}Z,b,a{ Г},b,a{
=
=Σ
;
:
δ
1)
)aZ,q( )Z,a,q(
0
0
=
δ
;
2)
{
}
)Z,q(), aaZ ,q( )aZ,a,q(
0
0
=
δ
;
3)
)bZ,q( )Z,b,q(
0
0
=
δ
- появилась недетерминированность;
4)
)bbZ ,q( )bZ,b,q(
0
0
=
δ
.
Однозначно можно сравнить и загрузить в автомат:
{
}
)bbZ ,q(),Z,q( )bZ,b,q(
0
1
0
=
δ
;
)baZ ,q( )aZ,b,q(
0
0
=
δ
;
)abZ ,q( )bZ,a,q(
0
0
=
δ
;
)e,q/()e,e,q( )Z,e,q(
2
2
1
=
δ
.
Рассмотрим aabbbbaa:
)Z,
aabbbbaa
,q(
0
|-
)aZ,
abbbbaa
,q(
0
|-
)aaZ , bbbbaa
,q(
0
|- ;
|-
) baaZ , bbbaa ,q(
0
(*
|-
) bbaaZ , bbaa ,q
0
|-
) baaZ ,baa ,q(
1
|- ;
|-
)aaZ ,aa,q(
1
|-
)aZ,a,q(
1
|-
)Z,e,q(
1
|-
)e,q(
2
.
Если автомат недетерминированный, его распознавательная способность
гораздо мощнее.
(*)
в этой ситуации автомат может воспользоваться вторым правилом: он может либо разгрузить, либо
перейти в состояние сравнения. Если он перейдёт в состояние сравнения, то цепочка принята не будет, так
как входная цепочка не пуста, следовательно нужно перейти в состояние загрузки
(**)
на данном шаге переходим в состояние сравнения, иначе магазин будет не пуст и цепочка принята не
будет.
