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

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

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

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

, где все символы имеют тот же смысл, что и в определении МП-автомата, за исключением того, что

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

- конечный выходной алфавит, а D - отображение множества Q x (T

{e}) x ? в множество конечных подмножеств множества

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

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

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

- состояние,

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

- цепочка на входной ленте,

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

- содержимое магазина,

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

- цепочка на выходной ленте, выданная вплоть до настоящего момента.

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

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

для любых

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

: Рефлексивно - транзитивное замыкание отношения

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

будем обозначать

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

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

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

для некоторых

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

. Переводом (или трансляцией), определяемым МП-преобразователем P (обозначается

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

), назовем множество

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

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

для всех
$Преобразователи с магазинной памятью$
и
$Преобразователи с магазинной памятью$
множество D(q, a, Z) содержит не более одного элемента,
если D(q, e, Z)

, то D(q, a, Z) =
для всех
$Преобразователи с магазинной памятью$
.

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

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

, в которой число вхождений символа 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 функцией переходов:

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

Содержание раздела

Главная сайта