Стр. 46 - Информационные структуры и их преобразование
Упрощенная HTML-версия
44
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
Пример:
}1 n/10{ L
nn
≥
=
=
2
1
0
q
q
q
Q
.
0
q
- загрузка (начальное состояние),
1
q
- сравнение,
2
q
- заключительное
состояние (принята или нет цепочка).
}Z,1,0{ Г},1,0{
=
=Σ
,
Z- начальные символы магазина;
МП=
{
}
2
0
2 1 0
q,Z,q,),Z,1,0(),1,0(),q,q,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 при q
0
;
4.
)Z,q(=)Z0,1,q(δ
1
1
- сравнение 1 и 0 при q
1
;
5.
)e,q(=)Z,e,q(δ
2
1
- убираем маркер.
I.
Рассмотрим допустимую цепочку 0011.
Загрузка начального (выделенного) состояния
)Z, 0011 ,q(
0
Итерация 1:
Входная цепочка пуста? Нет.
Сканирование символа входной цепочки 0.
Выполнение операций, задаваемых управляемым устройством
)Z, 0011 ,q(
0
|―
)Z0,011,q(
0
.
Магазин пуст? Нет.
Итерация 2:
Входная цепочка пуста? Нет.
Сканирование символа входной цепочки 0.
Выполнение операций, задаваемых управляемым устройством
)Z0,011,q(
0
|―
)Z00,11,q(
0
|.
Магазин пуст? Нет.
Итерация 3:
Входная цепочка пуста? Нет.
Сканирование символа входной цепочки 1.
Выполнение операций, задаваемых управляемым устройством
)Z00,11,q(
0
|―
)Z0,1,q(
1
|.
Магазин пуст? Нет.
Итерация 4:
Входная цепочка пуста? Нет.
Сканирование символа входной цепочки 1.
