|
|
|
|
|
|
|
| |
Автоматы с магазинной памятью |
Тематика: |
Математика |
Тип работы: |
реферат |
Размер файла: |
502 Кб |
С целью защиты от автоматических скачиваний, действительно, хочется убедится, что Вы человек, а не робот. Чтобы скачать реферат "Автоматы с магазинной памятью" введите, код изображенный на рисунке ниже. Зарегистрированным пользователям не нужно вводить код. Может стоит зарегистрироваться?
Не нашли подходящее? Попробуйте поискать тут:
дипломы на заказ, курсовые работы, рефераты на сайте findiplom.ru
|
|
Полный текст работы
Автоматы с магазинной памятью |
АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ
Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использованием бесконтекстных (контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во многих случаях можно рассматривать как бесконтекстные.
В отличие от конечных автоматов и преобразователей,
автоматы с магазинной памятью снабжены дополнительной магазинной памятью (рабочей лентой).
На рис. 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)>(q1, ?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
q1 = q, q2,..., qn+1 = q' Є Q
Существует два способа определения языка, допускаемого магазинным автоматом. Согласно первому способу считается, что входная цепочка ? Є V* принадлежит языку L1 (M) тогда, когда после просмотра последнего символа, входящего в эту цепочку,
в магазине автомата М будет находиться пустая цепочка ?. Другими словами,
L1 (M) = { ? | ?: (q0, z0) + * (q, ?)}
где q Є Q.
Согласно второму способу считается, что входная цепочка принадлежит языку L2 (M) тогда, когда после просмотра последнего символа, входящего в эту цепочку, автомат М окажется в одном из своих заключительных состояний qf Є F. Другими словами,
L2 (M) = { ? | ?: (q0, z0) + * (qf, ?)}
где ? Є V*m, qf Є F
Доказано, что множество языков, допускаемых произвольными магазинными автоматами согласно первому способу, совпадает с множеством языков, допускаемых согласно второму способу.
Доказано также, что если L (G2) - бесконтекстный язык, порождаемый Грамматикой G2 = (Vx, VT, Р, S), являющейся нормальной формой Грейбах, произвольной бесконтекстной грамматики G, то существует недетерминированный магазинный автомат М такой, что L1 (M) = L (G2). При этом
M = (V, Q, Vm , ?, q0, z0, 0),
Где V=VT; Q={q0}; VM=VN; z0=S
а для каждого правила G2 вида
A>a?, a Є VT, a Є V*n
строится команда отображения ?:
(q0, a, A)>(q0, a)
Apia логично для любого недетерминированного магазинного автомата М, допускающего язык L1 (M), можно построить бесконтекстную грамматику G такую, что L (G) = L1 (M).
Если для конечных автоматов детерминированные и недетерминированные модели эквивалентны по отношению к классу допускаемых языков, то этого нельзя сказать для магазинных автоматов. Детерминированные автоматы с магазинной памятью допускают лишь некоторое подмножество бесконтекстных языков, которые называют детерминированными бесконтекстными языками.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
КУЗИН Л.Т "Основы кибернетики" Т.2
УКРАИНСКИЙ ГОСУДАРСТВЕННЫЙ
ХИМИКО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ
Р Е Ф Е Р А Т
По дискретной математике на тему:
"Автоматы с магазинной памятью"
Подготовил студент гр. 1киб-30
Кирчатов Роман Романович
Преподаватель
Бразинская Светлана Викторовна
ДНЕПРОПЕТРОВСК, 2002
|
|
С целью защиты от автоматических скачиваний, действительно, хочется убедится, что Вы человек, а не робот. Чтобы скачать реферат "Автоматы с магазинной памятью" введите, код изображенный на рисунке ниже. Зарегистрированным пользователям не нужно вводить код. Может стоит зарегистрироваться?
|
Скачано: |
129 раз |
|
|
|
Работа (реферат/курсовая/диплом и т.п.) "Автоматы с магазинной памятью" и/или содержимое работы "Автоматы с магазинной памятью" предназначено исключительно для ознакомления,
без целей коммерческого использования. Все права в отношении работы "Автоматы с магазинной памятью" и/или
содержимого работ принадлежат их законным правообладателям. Администрация
сайта не несет ответственности за возможный вред и/или убытки, возникшие
или полученные в связи с использованием работы "Автоматы с магазинной памятью" и/или содержимого работы "Автоматы с магазинной памятью".
|
|
|
| |
Найти реферат |
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Зарегистрируйся и получи 25 Вт. ?
|
|
|
|
|
|
|
|
| |
 Время на сайте: 03:06:17 EEST
|
|
|
|
|
|
Автоматы с магазинной памятью (реферат) - Математика - Рефераты / банк рефератов, реферати, курсовая 
![СтудЗона [StudZona.com]](/img/logo.gif){kind=logo}
Рефераты
