Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Автоматы с магазинной памятью (MП-автоматы)




Рассмотрим понятие автомата с магазинной памятью – тип распознавателя, представляющий собой естественную модель синтаксических анализаторов контекстно-свободных языков. Автомат с магазинной памятью – это односторонний недетерминированный распознаватель, в потенциально бесконечной памяти которого элементы информации хранятся и используются так же, как патроны в магазине автоматического оружия, т.е. в каждый момент доступен только верхний элемент магазина. Распознаватель этого типа изображен на рисунке ниже.

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

Рис. 1. Автомат с магазинной памятью

 

Определение:Автомат с магазинной памятью (МП-автомат) – это упорядоченная семерка вида

,

где

-конечное множество состояний автомата;

-конечный входной алфавит;

-конечный алфавит магазинных символов;

-множество функций переходов автомата (отобра­жение множества вида в множество конечных подмножеств множества );

-начальное состояние автомата или управляющего устройства ();

-начальный символ магазина (символ, находящийся в магазине в начальный момент времени );

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

Определение:Конфигурацией автомата с магазинной памятью (МП-автомата) называется упорядоченная тройка вида

,

где

-текущее состояние автомата;

-неиспользованная или нерассмотренная часть входной цепочки (первый или самый левый символ находится над считывающей головкой), если , то входная цепочка уже прочитана;

-содержимое магазина (будем считать, что левый символ цепочки – это вершина стека), если , то магазин считается пустым.

Определение:Тактом работы автомата с магазинной памятью будем называть бинарное отношение вида

,

то есть переход из одной конфигурации в другую

,

если , где, , , , .

Индекс в отношении пишут для идентификации, к какому автомату относится данное бинарное отношение.

 

Соглашение: Далее будем считать эквивалентными обозначения - пустая цепочка и - пустой символ

 

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



Если , то верхний символ удаляется из магазина, и тем самым магазинный список сокращается.

Определение:Если , тогда входной символ из цепочки не считывается, но автомат может перейти в другое состояние и изменить содержимое магазина, такие такты называются -тактами.

Работа автомата заканчивается, если магазин пуст.

Определение:Начальной конфигурацией автомата будем называть тройку вида

,

где

- начальное состояние ();

- входная цепочка ();

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

Определение:Заключительной конфигурацией автомата будем называть тройку вида

,

где

, , -пустой символ.

Определение:Цепочка допускается МП-автоматом , если имеет место бинарное отношение вида

, (1)

где

- последовательность тактов работы автомата;

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

, , , .

Определение:Языком определяемым (или допускаемым) автоматом (обозначается ) называется множество цепочек , допускаемых автоматом , т.е.

Пример :

Построить МП-автомат, заданный следующим множеством

;

.

Решение:

Автомат будет выглядеть следующим образом

Построим функции перехода для МП-автомата (интуитивным способом)

;

;

;

;

;

.

 

Домашнее задание:Записать последовательность работы тактов МП-автомата для двух входных цепочек

;

.

Домашнее задание:Написать другие функции перехода МП-автомата (интуитивным способом), то есть написать свой МП-автомат.

Пример :

Построить МП-автомат, заданный следующим множеством

;

;

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

.

Решение:

Построим функции перехода для МП-автомата (интуитивным способом)

;

;

;

;

;

,

где

, , , .

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

.

.

 

Определение:Расширенным МП-автоматом назовем семерку вида

,

где

- конечное множество состояний автомата;

- конечный допустимый входной алфавит;

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

- отображение множества в множество конечных подмножеств множества ;

- начальное состояние автомата ();

- начальный символ магазина (символ, находящийся в магазине в начальный момент времени );

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

Определение:Конфигурация расширенного МП-автомата - это упорядоченная тройка вида

.

Определение:Начальной конфигурацией расширенного МП-автомата будем называть тройку вида

,

где

- начальное состояние;

- входная цепочка;

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

Определение:Заключительной конфигурацией расширенного МП-автомата будем называть тройку вида

,

где

, , -пустой символ.

Определение:Цепочка допускается расширенным МП-автоматом , если имеет место бинарное отношение вида

,

где

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

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

, , , , .

Определение:Языком, определяемым расширенным МП-автоматом , является множество вида

.

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

 

Пример :

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

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

.

Решение:

Приведем два варианта решения данного примера.

Вариант №1.

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

Правила грамматики имеют следующий вид

.

Построим функции перехода для расширенного МП-автомата (интуитивным способом)

,

,

,

,

,

.

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

.

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

.

 

Вариант №2.

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

Правила грамматики имеют следующий вид

.

Построим функции перехода для расширенного МП-автомата (интуитивным способом)

,

,

,

,

.

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

.

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

 





Дата добавления: 2014-01-07; Просмотров: 602; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.162.19.123
Генерация страницы за: 0.118 сек.