Стр. 47 - Информационные структуры и их преобразование
Упрощенная HTML-версия
45
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
Выполнение операций, задаваемых управляемым устройством
)Z0,1,q(
1
|―
)Z,e,q(
1
.
Магазин пуст? Да.
Входная цепочка пуста? Да.
Цепочка символов входного алфавита является допустимой.
II.
Рассмотрим недопустимую цепочку 001.
Загрузка начального (выделенного) состояния
)Z, 001 ,q(
0
.
Итерация 1:
Входная цепочка пуста? Нет.
Сканирование символа входной цепочки 0.
Выполнение операций, задаваемых управляемым устройством
)Z, 001 ,q(
0
|―
)Z0,01,q(
0
.
Магазин пуст? Нет.
Итерация 2:
Входная цепочка пуста? Нет.
Сканирование символа входной цепочки 0.
Выполнение операций, задаваемых управляемым устройством
)Z0,01,q(
0
|―
)Z00,1,q(
0
|.
Магазин пуст? Нет.
Итерация 3:
Входная цепочка пуста? Нет.
Сканирование символа входной цепочки 1.
Выполнение операций, задаваемых управляемым устройством
)Z00,1,q(
0
|―
)Z0,e,q(
1
|.
Магазин пуст? Нет.
Итерация 4:
Входная цепочка пуста? Да.
Цепочка символов входного алфавита является недопустимой.
Варианты МП-автоматов (доопределение)
То, что проходим с верхнего символа магазина не зависит от того, что
находится под ним:
)az,e,q()az ,w,q(
)z,e,q()z,w,q(
1
n
0
1
n
0
α
α
Знак "
" соответствует знаку "|-".
Рассмотренным МП-автоматом называется цепочка символов
{
}
F,z,q,,,,Q
0 0
δΓΣ
, где
δ
- отображение.
