Алгоритм построения расширенного МП-автомата по произвольной КС-грамматике

Вход: - произвольная КС-грамматика.

Выход: - расширенный МП-автомат.

Метод:

1. Множество состояний расширенного МП-автомата примет вид ;

2. Входной алфавит расширенного МП-автомата совпадает с алфавитом терминальных символов исходной грамматики;

3. Алфавит магазинных символов будет следующим ;

4. Начальным состоянием будет единственное состояние, т.е. ;

5. Начальным магазинным символом будет целевой символ КС-грамматики ;

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

7. Определим множество расширенного МП-автомата следующим образом:

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

b. Во множество функций перехода автомата добавляются все переходы вида для , . Здесь на этих тактах входные символы переносятся в магазин.

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

Пример:

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

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

Решение:

1. Расширенный МП-автомат будет иметь вид ,

где функции перехода будут следующие

,

,

,

,

.

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

a. Последовательность тактов работы автомата для цепочки будет иметь вид

;

b. Последовательность тактов работы автомата для цепочки будет иметь вид

.

Домашнее задание: П остроить для нижеследующей грамматики расширенный МП-автомат

.

И построить последовательность тактов работы расширенного МП-автомата для цепочки

.

Домашнее задание (убрать в практику): Построить расширенный МП-автомат для грамматики вида

,

где

.

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

.

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