Теория и реализация языков программирования



         

Преобразователи с магазинной памятью


Рассмотрим важный класс абстрактных устройств, называемых преобразователями с магазинной памятью. Эти преобразователи получаются из автоматов с магазинной памятью, если к ним добавить выход и позволить на каждом шаге выдавать выходную цепочку.

Преобразователем с магазинной памятью (МП-преоб- разователем) называется восьмерка

P = (Q, T, \Gamma, \Pi, D, q_0, Z_0, F)
, где все символы имеют тот же смысл, что и в определении МП-автомата, за исключением того, что
\Pi
- конечный выходной алфавит, а D - отображение множества Q x (T
{e}) x ? в множество конечных подмножеств множества
Q \times \Gamma^* \times \Pi^*
.

Определим конфигурацию преобразователя P как четверку (q, x, u, y), где

q \in Q
- состояние,
x \in T^*
- цепочка на входной ленте,
u \in \Gamma^*
- содержимое магазина,
y \in \Pi^*
- цепочка на выходной ленте, выданная вплоть до настоящего момента.

Если множество D(q, a, Z) содержит элемент (r, u, z), то будем писать

(q, ax, Zw, y) \vdash^* (r, x, uw, yz)
для любых
x \in T^*
,
w \in \Gamma^*
и
y \in \Pi^*
: Рефлексивно - транзитивное замыкание отношения
\vdash
будем обозначать
\vdash^*
.

Цепочку y назовем выходом для x, если

(q_0, x, Z_0, e) \vdash^* (q, e, u, y)
для некоторых
q in F
и
u \in \Gamma^*
. Переводом (или трансляцией), определяемым МП-преобразователем P (обозначается
\tau(P)
), назовем множество

\{(x,y) \mid (q_0,x,Z_0,e) \vdash^* (q,e,u,y)\} \text{ для некоторых } q \in F \text{ и } u \in \Gamma^*

Будем говорить, что МП-преобразователь P является детерминированным (ДМП-преобразователем), если выполняются следующие условия:

  1. для всех
    q \in Q, a \in T \cup \{e\}
    и
    Z \in \Gamma
    множество D(q, a, Z) содержит не более одного элемента,
  2. если D(q, e, Z)
    , то D(q, a, Z) =
    для всех
    a \in T
    .

Пример 5.1. Рассмотрим перевод ? , отображающий каждую цепочку

x \in \{a, b\}^* \$
, в которой число вхождений символа a равно числу вхождений символа b, в цепочку y = (ab)n, где n - число вхождений a или b в цепочку x. Например, ? (abbaab$) = ababab.

Этот перевод может быть реализован ДМП-преобразователем P = ({q0, qf}, {a, b, $}, {Z, a, b}, {a, b}, D, q0, Z, {qf}) c функцией переходов:

\begin{align*} & D(q_0, X, Z) = \{(q_0, XZ, e)\}, X \in \{a, b\}, \\ & D(q_0, \$, Z) = \{(q_f, Z, e)\}, \\ & D(q_0, X, X) = \{(q_0, XX, e)\}, X \in \{a, b\}, \\ & D(q_0, X, Y ) = \{(q_0, e, ab)\}, X \in \{a, b\}, Y \in \{a, b\}, X \neq Y . \end{align*}




Содержание  Назад  Вперед