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

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

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

Метод:

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

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

;

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

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

,

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

,

где

, , , ,

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

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

,

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

;

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

,

где .

Пример:

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

,

,

,

,

,

,

.

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

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

Решение:

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

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

;

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

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

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

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

;

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

;

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

;

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

;

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

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

;

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

.

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

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

.

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