АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ
Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использованием бесконтекстных (контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во многих случаях можно рассматривать как бесконтекстные.
В отличие от конечных автоматов и преобразователей
,
автоматы с магазинной памятью
снабжены дополнительной магазинной памятью (рабочей лентой).
На рис. 1
такой преобразователь. Конечное управляющее устройство снабжается дополнительной управляющей головкой, всегда указывающей на
верхнюю ячейку магазинной памяти; за один такт работы автомата (преобразователя) управляющая головка может произвести следующие движения:
1) стереть символ из верхней ячейки (при этом все символы, находящиеся на рабочей ленте, перемещаются на одну ячейку вверх);
2) стереть символ из верхней ячейки и записать на рабочую ленту непустую цепочку символов (при этом содержимое
рабочей ленты сдвигается вниз ровно настолько, какова длина
с записываемой цепочки).
Таким образом, устройство магазинной памяти можно сравнить с устройством магазина боевого автомата: когда в него вкладывается патрон, те, которые уже были внутри, проталкиваются вниз; достать можно только патрон, вложенный последним.
Формально детерминированный магазинный
автомат
определяется как следующая совокупность объектов:
M = (V, Q, VM
,
δ, q0
, z0
, F),
где V, Q, q0
Є
Q, F определяются так же, как и для конечного автомата;
VM
= {z0
, z1
,…,zp
-1
} — алфавит магазинных символов автомата;
δ — функция, отображающая множество Q
X
(
V
U
{
ε })
X
VM
в множество Q
X
VM
, где е — пустая цепочка;
z0
Є
VM
— так называемый граничный маркер, т. е. символ,
первым появляющийся в магазинной памяти.
Недетерминированный магазинный автомат
отличается от детерминированного только тем, что функция δ отображает множество Q
X
(
V
U
{
ε })
X
VM
. в множество конечных подмножеств Q
x
VM
Как и в случае конечных автоматов, преобразователи с магазинной памятью отличаются от автоматов с магазинной памятью наличием выходной ленты.
Далее будем рассматривать только недетерминированные магазинные автоматы.
Рассмотрим интерпретацию функции δ
для такого автомата. Эту функцию можно представить совокупностью команд вида
(q, a, z)→(q1
, γ1
),…,(qm
, γm
),
гдеq, q1
,…qm
Є Q, a Є V, z Є VM
, γ1
,…,γm
Є V*
m
При этом считается, что если на входе читающей головки авто
мата находится символ а
, автомат находится в состоянии q
, а верхний символ рабочей ленты z
, то автомат может перейти к состоянию qi
, записав при этом на рабочую ленту цепочку γi
(1 ≤ i ≤ m)
вместо символа z
, передвинуть входную головку на один символ
вправо так, как это показано на рис. 1, и перейти в состояние qi
. Крайний левый символ γi
должен при этом оказаться в верхней
ячейке магазина. Команда (
q
,
e
,
z
)→(
q
1
,
γ
1
),…, (
qm
,
γm
)
означает,
что независимо от входного символа и, не передвигая входной го- +
ловки, автомат перейдет в состояние qi
, заменив символ z
магазина
на цепочку γi
(1 ≤
i
≤
m
).
•
Ситуацией магазинного автомата
называется пара (
q
,
γ
)
, где
q
Є
Q
, γ
Є
V
*
m
. Между ситуациями магазинного автомата (
q
,
γ
)
и
(
q
’,
γ
’)
, устанавливается отношение, обозначаемое символом ├, если среди команд найдется такая, что
(q, a, z)→(q1
, γ1
),…,(qm
, γm
),
причемγ= zβ, γ’ = γi
β q
' = qi
длянекоторого1 ≤ i ≤ m (z
Є
Vm
,
β
Є
V*
m
).
Говорят, что магазинный автомат переходит из состояния (
q
,
γ
)
в состояние (
q
’,
γ
’)
и обозначают это следующим образом:
a: (q, γ)├ (q’, γ’)
.
Вводится и такое обозначение:
a1
...an
: (q, γ)├
*
(q’, γ’),
если справедливо, что
ai
: (qi
, γi
)├ (qi+1
, γi+1
), 1 ≤ i ≤ m
где
ai
Є
V
,
γ
1
=
γ
,
γ
2
,…,
γn
+1
=
γ
’ Є
V
*
m
q
1
=
q
,
q
2
,…,
qn
+1
=
q
’ Є
Q
Существует два способа определения языка, допускаемого магазинным автоматом. Согласно первому способу считается, что входная цепочка α
Є
V
*
принадлежит языку L
1
(
M
)
тогда, когда после просмотра последнего символа, входящего в эту цепочку,
в магазине автомата М
будет находиться пустая цепочка ε
. Другими словами,
L1
(M) = {
α
|
α
: (q0
, z0
) ├
*
(q,
ε
)}
где q
Є
Q
.
Согласно второму способу считается, что входная цепочка принадлежит языку L
2
(
M
)
тогда, когда после просмотра последнего символа, входящего в эту цепочку, автомат М
окажется в одном из своих заключительных состояний q
f
Є
F
. Другими словами,
L
2
(
M
) = { α | α: (
q
0
,
z
0
) ├
*
(
qf
,
γ
)}
где γ
Є
V
*
m
,
qf
Є
F
Доказано, что множество языков, допускаемых произвольными магазинными автоматами согласно первому способу, совпадает с множеством языков, допускаемых согласно второму способу.
Доказано также, что если L
(
G
2
)
— бесконтекстный язык, порождаемый Грамматикой G2
= (
Vx
,
VT
,
Р,
S
)
, являющейся нормальной формой Грейбах, произвольной бесконтекстной грамматики G
, то существует недетерминированный магазинный автомат М такой, что L
1
(
M
) =
L
(
G
2
).
При этом
M = (V, Q, Vm
, δ, q0
, z0
, 0),
ГдеV=VT
; Q={q0
}; VM
=VN
; z0
=S
а для каждого правила G
2
вида
A→a
α
, a
Є
VT
, a
Є
V*
n
строится команда отображения δ
:
(q0
, a, A)→(q0
, a)
Apia логично для любого недетерминированного магазинного автомата М
, допускающего язык L
1
(
M
)
, можно построить бесконтекстную грамматику G
такую, что L
(
G
) =
L
1
(
M
).
Если для конечных автоматов детерминированные и недетерминированные модели эквивалентны по отношению к классу допускаемых языков, то этого нельзя сказать для магазинных автоматов. Детерминированные автоматы с магазинной памятью допускают лишь некоторое подмножество бесконтекстных языков, которые называют детерминированными бесконтекстными языками.
Список использованной литературы
КУЗИН Л.Т «Основы кибернетики» Т.2
УКРАИНСКИЙ ГОСУДАРСТВЕННЫЙ
ХИМИКО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ
Р Е Ф Е Р А Т
По дискретной математике на тему:
«Автоматы с магазинной памятью»
Подготовил студент гр. 1киб-30
Кирчатов Роман Романович
Преподаватель
Бразинская Светлана Викторовна
ДНЕПРОПЕТРОВСК, 2002
Другие работы по теме:
Торговые автоматы
Торговый автомат – монетное устройство для продажи товаров. Автоматы принимают монеты с помощью монетоприемника и купюры посредством купюроприемника.
Кодовый замок
Содержание. 1). Задание на проектирование. -2- 2). Введение. -2- 3). Абстрактный синтез автомата.-5- 4). Структурный синтез автомата. -8- 5). Набор элементов для физического синтеза. -8-
Налогообложение 2 Расчет суммы
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО – ЭКОНОМИЧЕСКИЙ ИНСТИТУТ КОНТРОЛЬНАЯ РАБОТА ПО НАЛОГАМ И НАЛОГООБЛОЖЕНИЮ
Сварочное оборудорвание
3 Сварочное оборудование 3.1 Оборудование для сварки неплавящимся электродом в защитном газе Простейшие автоматы для аргонодуговой сварки неплавящимся электродом без подачи присадочной проволоки обеспечивают горение сварочной дуги между электродом и изделием, газовую защиту электрода, сварочной ванны и прилегающего к ней металла от воздействия воздуха, передвижение дуги вдоль свариваемых кромок.
Шпоры по теории автоматов
Билет №1 Определение ЦА. Основные понятия теории автоматов: ЦА конечные, синхронные, асинхронные, идеализированные, абстрактные, структурные. Абстрактная и структурная теория автоматов.
Секретные принципы превосходной памяти
Вы сможете запоминать и воспроизводить тысячи фактов используя факторы, лежащие в основе совершенной памяти: воображение и ассоциацию. В Древней Греции и Риме их осваивали сенаторы с целью поразить публику выдающимися способностями.
Память
Памятью называется психическое явление, заключающееся в закреплении, сохранении и воспроизведении индивидом прошлого опыта. В число основных процессов памяти входят запоминание, сохранение, воспроизведение, а также забывание ранее закрепленного.
Хорошо организованная память
Человек, не обладающий хорошей профессиональной памятью, может начать развитие своих мнемонических способностей путем постоянного применения этих правил.
Эмоциональная память
Эмоциональная память. Следует начать на самом понятии «память». В широком смысле слова под биологической памятью понимают свойство живой системы хранить след от воспринятого раздражения. В такой общей формулировке понятие «память» объемлет очень широкий спектр явлений, в связи с чем, говоря о памяти высших животных и человека, предпочтительно подразумевать способность организма в процессе своей индивидуальной жизни запечатлевать, хранить, воспроизводить и забывать воспринятую информацию.
Состав домового электрощитка
Местом средоточения всея электрики в каждом доме или квартире является домовой электрический щит. Именно здесь при помощи различной аппаратуры происходит распределение электрической энергии по вашему жилищу.
Кодовый замок
Цель данной работы - спроектировать автомат «кодовый замок», имеющий три информационных входа: A, B, C, на которые подается входной сигнал в восьмеричном коде, и два выхода Z1, Z2.
Автоматы с магазинной памятью
Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использованием бесконтекстных (контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во многих случаях можно рассматривать как бесконтекстные.
Чем привлекает меня Шерлок Холмс
Вот уже на протяжении нескольких столетий люди захватываются талантливым детективом Шерлоком Холмсом, испытывают удивление его способностям. А создал героя своим воображением и художественным мастерством английский писатель Артур Конан Дойль, который считал, что для того чтобы познать человечество, надо выучить и исследовать человека.
Идейно-художественное своеобразие книги Бунина Темные аллеи.
Автор: Бунин И.А. Книга «Темные аллеи» принадлежит к шедеврам мировой литературы, писатель работал над ней с 1937 по 1949 годы. Судьба книги была сложная, впервые она была опубликована в 1943 году в Нью-Йорке тиражом в 600 экземпляров (11 из 20 произведений вошли в нее). Лишь в 1946 году выходит парижское издание книги (38 произведений).
У войны не женское лицо по повести Бориса Васильева А зори здесь тихие
У войны не женское лицо 8230 по повести Бориса Васильева А зори здесь тихие 8230 У каждого человека свое представление о войне. Для одних война — это разрушения, холод, голод, бомбежки; для других — сражения, подвиги, герои. Совсем иной видит войну Б. Васильев. В его повести "А зори здесь тихие..." нет захватывающих батальных сцен, мужественных героев, но, возможно, именно в этом ее прелесть.
Не устану следить, чтобы Вечный огонь не погас...
Автор: Разное В годы Великой Отечественной войны погиб каждый четвертый житель нашей страны. Каждая семья недосчитала своих родных и близких. Каждый четвертый стал вечной памятью живых. Многие деревни были сожжены вместе с жителями. Эту войну до сих пор помнят люди. А ведь многие никогда не задумывались о том, зачем мы помним и помогаем тем людям, которые спасли нашу родину.
Литература на военную тему
Каждому русскому человеку особенно дорог Праздник Победы. Дорог памятью о тех, кто ценою своей жизни отстаивал свободу. Мы должны всегда помнить о людях, отдавших свои жизни за свободу и светлое будущее нашей страны.
Виды розничной торговой сети
Реферат на тему: «Виды розничной торговой сети» В зависимости от способа и условий обслуживания покупателей, характера устройства и оборудования торговых предприятий, а также техники торгово-оперативного процесса различают три основных вида розничной торговой сети: стационарную, передвижную и посылочную торговлю.
Описание схемы автомата световых эффектов Бегущие огни
1 ОПИСАНИЕ СХЕМЫ АВТОМАТА СВЕТОВЫХЭФФЕКТОВ «БЕГУЩИЕ ОГНИ» Трехфазный мультивибратор собран на транзисторах VT1-VT3, в их коллекторные цепи включены светодиоды HL1-HL12, разделенные на три группы по четыре последовательно. Транзисторы поочередно открываются и включают соответствующие светодиоды.
Автомат
Слово "автомат" в переводе с древнегреческого языка означает "самодействующий". Человечеству самодействующие устройства известны с древнейших времен. Еще в эпоху фараонов в Египте были созданы механизмы, которые "сами" открывали двери храмов.
Гражданская война в Сальвадоре
Гражданская война в Сальвадоре (исп. Guerra Civil de El Salvador) — война в Сальвадоре между правительством страны и народно-патриотическими партизанскими силами, объединёнными во Фронт национального освобождения имени Фарабундо Марти.
Архитектура памяти Windows CE 6
Вкратце, новая модель памяти дает возможность для запуска практически неограниченного числа процессов и под каждый процесс выделяется 2Гб виртуальной памяти.
Свободная Память
Если вы пользовались классом slist, вы могли обнаружить, что ваша программа тратит на заметное время на размещение и освобождение объектов класса slink.
Микроконтроллеры семейства MCS51 Intel
Инструкции MCS51 Intel Инструкции, модифицирующие флаги (1) Инструкция C OV AC Инструкция C OV AC CLR C ADDC CPL C SUBB ANL C,bit ANL C,/bit ORL C,bit ORL C, bit
Bios
Введение Хорошо известно, что производительность Вашей материнской платы сильно зависит от временных установок для работы с памятью, выполняемых в BIOS Setup. Название пунктов Setup, в которых устанавливаются эти временные параметры может меняться в зависимости от чипсета и BIOS на Вашей матернской плате.
КЭШ память с прямым распределением
Принципы построения КЭШ - памяти с прямым распределением. Стратегия размещения и механизм преобразования адресов в кэш-памяти с прямым отображением.
Устройства ЭВМ: КЭШ-память
Кэш-память – это высокоскоростная память произвольного доступа, используемая процессором компьютера для временного хранения информации.
Устройство ПК 3
Персональные компьютеры имеют четыре иерархических уровня памяти: микропроцессорная память; основная память; регистровая кэш-память; внешняя память.
Рамеев Башир Искандарович
Автор первого в стране проекта цифровой ЭВМ с жестким программным управлением, завершенный за несколько месяцев до начала работ над МЭСМ.