Стр. 78 - Информационные структуры и их преобразование

76 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Рассмотрим автомат: ( q0, q1 , a, b, δ, q0, q1 , e);
δ( q 0, a) = (q 0, b);
δ( q 0, e) = (q 0, b);
(q0 , a, e) |→ (q1 , e, b) |→ (q1 , e, b)
Нужно в заключительном состоянии запретить е – такты.
5.4. Преобразователи с магазинной памятью
Они могут быть получены путем добавления автомату с магазинной
памятью выходной цепочки.
МП – преобразователь содержит 8 символов:
{Q, Σ, Г, ∆, δ, q0 , Z, F}, где все элементы означают то же, что и раньше,
кроме функции отображения:
δ: Q* Σ*Г -> Q1 *Г**∆* , где Σ - входной символ, Г – магазинный символ.
Конфигурация содержит 4 символа:
(q, aw, z, y),
где q – состояние;
aw – входная цепочка;
z – магазин;
y - входная цепочка.
δ (q, a, γz) = (q1 , αz, β) – функция отображения;
(q, aw, γz, y)| (q1 , w, αz, yβ) Записывают только верх магазина
(γz, αz), дно не пишут.
Цепочку y называют выходом цепочки x, если:
(q, х, z, y)| (q1, w, α, y).
Преобразователь переводит цепочку х в цепочку у опустошением
магазина только тогда, когда имеет место следующее:
q1
a / b
e / b
q0
a
+