Алгоритм построения МП-преобразователя для простой СУ-схемы

Эквивалентность простых СУ-схем и преобразователей с магазинной памятью

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

Вход: - простая СУ-схема.

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

Метод:

Идея метода: При моделировании правила схемы преобразователь заменит в магазине верхний символ цепочкой , в которую вставлены выходные символы из цепочки , т.е. если и , то символ будет заменен цепочкой . Надо уметь, однако, отличать символы алфавита от символов алфавита , чтобы можно было правильно разбивать цепочки на две части. Если и не пересекаются, то никакой проблемы нет. В общем случае определим новый алфавит , соответствующий , но заведомо не пересекающийся с . Будем считать, что состоит из новых символов , соответствующих . Тогда и естественно определить такой гомоморфизм , что для , т.е.

,

.

1. Строим гомоморфизм и определяем новый алфавит по принципам, изложенным выше .

2. Множество состояний МП-преобразователя примет вид ;

3. Входной алфавит МП-преобразователя совпадает со входным алфавитом СУ-схемы;

4. Алфавит магазинных символов МП-преобразователя будем иметь следующий вид ;

5. Выходной алфавит МП-преобразователя совпадает с выходным алфавитом СУ-схемы;

6. Начальным состоянием МП-преобразователя будет состояние ;

7. Начальным символом магазина МП-преобразователя будет целевой символ СУ-схемы ;

8. Множество заключительных состояний МП-преобразователя делаем пустым, т.к. рассматривается перевод, определяемый МП-преобразователем, допускающим опустошение магазина;

9. Множество переходов МП-преобразователя, допускающего опустошение магазина, строим следующим образом:

a. Если во множестве правил присутствуют правила вида

,

где

;

- нетерминалы ;

- символы входного алфавита;

- символы выходного алфавита;

тогда во множество функций переходов добавляем переход вида

;

b. Во множество добавляем все переходы вида

;

c. Во множество добавляем все переходы вида

.

Пример:

Пусть дана СУ-схема вида , правила которой определяется следующим образом

и задан гомоморфизм вида

, , .

1. Необходимо построить МП-преобразователь, допускающий опустошение магазина.

2. Написать такты работы МП-преобразователя, полученного в предыдущем примере, для входной цепочки вида

Решение:

1. МП-преобразователь будет иметь вид , множество функций перехода которого примет вид

,

,

,

,

,

,

.

2. Последовательность тактов работы МП-преобразователя для цепочки примет вид

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