Алгоритм построения по МП-автомату МП-автомата, допускающего цепочки опустошением магазина

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

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

Метод:

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

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

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

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

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

5. - начальное состояние автомата ;

6. - множество заключительных состояний автомата ;

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

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

a. Если множество содержит переход вида , то будет содержать для , , ;

b. Добавим переход вида , то есть на первом такте автомат записывает в магазин и переходит в начальное состояние автомата (играет роль маркера, отмечающего дно магазина);

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

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

Пример:

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

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

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

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

Решение:

1. МП-автомат имеет вид

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

;

;

;

;

;

.

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

a. Множество состояний результирующего автомата будет иметь вид ;

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

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

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

e. - начальное состояние автомата ;

f. - множество заключительных состояний автомата ;

e. Определим множество результирующего автомата следующим образом:

i. Добавим в множество переходы вида

,

,

,

,

,

;

ii. Добавим в множество переход вида

;

iii. Добавим в множество переход вида

,

,

;

iv. Добавим в множество переход вида

,

,

.

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

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

.

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

.

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

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