Алгоритм построения МП-автомата по расширенному МП-автомату

Соотношения между различными МП-автоматами

Лемма: Для любого МП-автомата можно построить расширенный
МП-автомат и наоборот.

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

Выход: - МП-автомат.

Метод:

1. Положим .

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

2. Итак, положим , где каждый элемент семерки определяется следующим образом:

a. - входной алфавит результирующего автомата;

b. - начальный символ магазина результирующего автомата;

c. - алфавит магазинных символов результирующего автомата;

d. - множество возможных состояний автомата

e. Множество функций переходов результирующего автомата определяется следующим образом:

i. Допустим, что . Тогда

1. если , то

для ,

где и ;

2. если , то

для ;

ii. Функции вида

для .

Эти правила осуществляют заполнение буфера управляющего устройства, который содержит символов.

f. Начальное состояние результирующего автомата будет иметь вид . То есть в начальный момент буфер содержит наверху и символов пониже. Символы используются как специальные маркеры, отмечающие «дно», т.е. нижний конец магазина.

g. Множество заключительных состояний результирующего автомата примет вид

.

Пример:

Для расширенного МП-автомата из примера:

1. построить эквивалентный МП-автомат ;

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

3. сравнить полученный МП-автомат и последовательность тактов работы МП-автомата с МП-автоматом и последовательностью тактов работы данного автомата из примера.

Решение:

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

,

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

,

,

,

,

.

Построим эквивалентный МП-автомат . Здесь каждый элемент примет соответственно следующий вид

a. Положим . В нашем случае .

b. - алфавит входных символов результирующего автомата;

c. - начальный символ магазина;

d. - алфавит магазинных символов;

e. - множество возможных состояний МП-автомата, которое примет вид

f. Множество функций переходов результирующего автомата определим следующим образом:

i. Для функции в множество добавим переходы вида для , , , где и .

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

ii. Для функции в множество добавим переходы вида для , , , где и .

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

iii. Для функции в множество добавим переходы вида для , , , где и .

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

iv. Для функции в множество добавим переходы вида для , , .

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

v. Для функции в множество добавим переходы вида для , , .

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

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

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

g. Начальное состояние результирующего автомата будет иметь вид

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

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

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

.

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

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

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