2.1.1.3. Конечные преобразователи

Введем наш простейший транслятор – конечный преобразователь. Преобразователь – это просто распознаватель, выдающий на каждом такте выходную цепочку (она может быть и пустой). Конечный преобразователь получится, если конечному автомату (распознавателю) позволить выдавать на каждом такте цепочку выходных символов.

Рис. 2. Конечный преобразователь

Для большей общности рассмотрим в качестве основы конечного преобразователя недетерминированный конечный автомат, способный делать -такты.

Определение: Конечный преобразователь - это упорядоченная шестерка вида

,

где

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

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

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

- множество функций переходов (отображение множества в множество конечных подмножеств множества );

- начальное состояние автомата ( );

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

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

,

где

- текущее состояние управляющего устройства (текущее состояние преобразователя);

- непрочитанная часть входной цепочки, причем самый левый символ цепочки находится над считывающей головкой ( );

- выходная цепочка, выданная вплоть до текуще­го момента ( ).

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

,

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

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

, ,

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

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

.

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

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

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

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

,

где

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

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

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

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

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

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

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

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

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

,

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

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

,

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

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

,

где

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

;

;

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

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

,

где

;

;

;

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

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

, , ,

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

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

.

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

.

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

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

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

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

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

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

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