Готовые Домашние Задания

Рефераты по теме Маркетинг

Реферат Автоматы с магазинной памятью

Скачать реферат↓ [8.07 KB]



Текст реферата Автоматы с магазинной памятью

АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ
Автоматы и преобразователи с магазинной памятью играют важную роль при
построении автоматнолингвистических моделей различного назначения,
связанных с использованием бесконтекстных (контекстносвободных)
языков. В частности, такие устройства используются в большинстве
работающих программ для синтаксического анализа программ, написанных
на различных языках программирования, которые во многих случаях можно
рассматривать как бесконтекстные.
В отличие от конечных автоматов и преобразователей,
автоматы с магазинной памятью снабжены дополнительной магазинной
памятью (рабочей лентой).
На рис. 1
такой преобразователь. Конечное управляющее устройство снабжается
дополнительной управляющей головкой, всегда указывающей на
верхнюю ячейку магазинной памяти; за один такт работы автомата
(преобразователя) управляющая головка может произвести следующие
движения:
1) стереть символ из верхней ячейки (при этом все символы,
находящиеся на рабочей ленте, перемещаются на одну ячейку вверх);
2) стереть символ из верхней ячейки и записать на рабочую ленту
непустую цепочку символов (при этом содержимое
рабочей ленты сдвигается вниз ровно настолько, какова длина
с записываемой цепочки).
Таким образом, устройство магазинной памяти можно сравнить с
устройством магазина боевого автомата: когда в него вкладывается
патрон, те, которые уже были внутри, проталкиваются вниз; достать
можно только патрон, вложенный последним.
Формально детерминированный магазинный автомат определяется как
следующая совокупность объектов:
M = (V, Q, V M , д , q 0 , z 0 , F),
где V , Q , q 0 Є Q , F определяются так же, как и для конечного
автомата;
V M = z 0 , z 1 ,…, z p -1 — алфавит магазинных
символов автомата;

д — функция, отображающая множество Q X ( V U е ) X V M

в множество Q X V M , где е — пустая цепочка;
z 0 Є V M — так называемый граничный маркер, т. е. символ,
первым появляющийся в магазинной памяти.
Недетерминированный магазинный автомат отличается от
детерминированного только тем, что функция д отображает множество
Q X ( V U е ) X V M . в множество конечных подмножест
в Q x V M
Как и в случае конечных автоматов, преобразователи с магазинной
памятью отличаются от автоматов с магазинной памятью наличием выходной
ленты.
Далее будем рассматривать только недетерминированные магазинные
автоматы.
Рассмотрим интерпретацию функции д для такого автомата. Эту
функцию можно представить совокупностью команд вида

(q, a, z)→'3f(q 1 , г 1 ),…,(q m , г m ),
где q, q 1 ,…q m Є Q, a Є V, z Є V M , г 1 ,…,г m Є V * m
При этом считается, что если на входе читающей головки авто
мата находится символ а , автомат находится в состоянии q , а верхний
символ рабочей ленты z , то автомат может перейти к состоянию q i ,
записав при этом на рабочую ленту цепочку г i (1 ≤'3d i
≤'3d m )
вместо символа z , передвинуть входную