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

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

2.1.1.5.1. Алгоритм построения мп-преобразователя для простой су-схемы

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

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

Метод:

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

,

.

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

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

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

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

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

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

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

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

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

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

,

где

;

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

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

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

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

;

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

;

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

.

Пример :

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

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

, , .

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

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

Решение:

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

,

,

,

,

,

,

.

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

2.1.1.5.2. Алгоритм построения простой су-схемы по мп-преобразователю

Вход: - МП-преобразователь.

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

Метод:

Идея метода: Построение схемы аналогично построению КС-грамматики по МП-автомату.

1. Множество нетерминалов СУ-схемы примет вид

;

2. Строим множество правил СУ-схемы:

   1. Если существует переход вида

,

то во множество правил добавляются правила вида

,

где

, , , ,

- любая последовательность состояний;

2. Если существует переход вида

,

то добавляются правила вида

;

3. Добавляем правила вида

,

где .

Пример :

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

,

,

,

,

,

,

.

(МП-преобразователь из предыдущего примера)

2. Построить вывод для цепочки .

Решение:

1. Построим СУ-схему , где

   1. Множество нетерминалов примет

;

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

3. Определим множество правил СУ-схемы следующим образом

   1. Для перехода добавляем правило вида

2. Для перехода добавляем правило

;

3. Для перехода добавляем правило

;

4. Для перехода добавляем правило

;

5. Для перехода добавляем правило

;

6. Для перехода добавляем правило ;

7. Для перехода добавляем правило

;

8. Добавляется правило вида

.

2. Переобозначим построенную СУ-схему , где правила примут вид

3. Построим вывод для цепочки :

.