Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
эл.лекции.doc
Скачиваний:
4
Добавлен:
01.05.2025
Размер:
7 Мб
Скачать
☆

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

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

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

Метод:

Идея метода: МП-автомат по определению является расширенным !!!

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

1.5.3. МП-автоматы, опустошающие магазин

Рассмотрим МП-автоматы, которые могут по входным цепочкам опустошать магазин.

Определение: Пусть - МП-автомат. Будем говорить, что допускает цепочку опустошением магазина, если для некоторого . Пусть - множество цепочек, допускаемым автоматом опустошением магазина.

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

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

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

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

Метод:

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример :

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

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

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

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

Решение:

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

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

;

;

;

;

;

.

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

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

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

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

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

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

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

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

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

,

,

,

,

,

;

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

;

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

,

,

;

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

,

,

.

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

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

.

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

.

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