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

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

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

,

где

- конечное множество состояний преобразователя;

- конечный входной алфавит;

- конечный алфавит магазинных символов;

- конечный выходной алфавит;

- множество переходов преобразователя (отображение множества вида в множество конечных подмножеств множества );

- начальное состояние;

- начальное состояние магазина;

- множество заключительных состояний;

Определение: Конфигурацией преобразователя с магазинной памятью называется упорядоченная четверка вида

,

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

Определение: Тактом работы конечного преобразователя с магазинной памятью называется бинарное отношение вида (или когда ясно о каком МП-преобразователе идет речь), определяющееся на конфигурациях преобразователя,, т.е.

,

если , где , , , , , , .

Определение: Начальной конфигурацией преобразователя будем называть четверку вида

,

где

- начальное состояние;

;

;

-пустой символ.

Определение: Заключительной конфигурацией преобразователя с магазинной памятью будем называть четверку вида

,

где

;

;

;

-пустой символ.

Определение: Цепочку назовем выходом для цепочки , если

, , ,

т.е. МП-преобразователь переходит из начальной конфигурации в заключительную.

Определение: Переводом (или преобразованием), определяемым МП-преобразователем (обозначается ) называется множество вида

.

Определение: Переводом (или преобразованием), определяемым МП-преобразователем опустошением магазина называем множество вида

.

Домашнее задание:

Самостоятельно написать следующие определения:

1. расширенного МП-преобразователя;

2. конфигурации расширенного МП-преобразовател;

3. такта работы расширенного МП-преобразователя;

4. начальной и заключительной конфигурации МП-преобразователя;

5. перевода (или преобразования), определяемого МП-преобразователем;

Дата добавления: 2014-01-07