Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Автоматы с магазинной памятью
Раздел: Рефераты по математике
Тип: реферат Добавлен 19:47:56 06 сентября 2005 Похожие работы
Просмотров: 223 Комментариев: 3 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

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

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

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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений22:21:05 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
11:31:07 29 ноября 2015
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
11:52:41 24 ноября 2015

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

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(149958)
Комментарии (1829)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru