Реферат: Автоматы с магазинной памятью - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

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

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 168 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!

Узнайте стоимость написания уникальной работы




АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ



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

В отличие от конечных автоматов и преобразователей,
автоматы с магазинной памятью снабжены дополнительной магазинной памятью (рабочей лентой).

На рис. 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

1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Один чудак назвал своего сына именем Гораг. Теперь ждёт рождения внучки, чтобы поржать над её отчеством...
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по математике "Автоматы с магазинной памятью", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru