|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[8] Выход. Магазинный автомат M(D), определяемый шагом 3 алгоритма. Шаг 1. PPDA := 0; VPDA := {[P0, Z0]}. Шаг 2. Пока множество VPDA пополняется новыми вершинами, выполнять следующие два действия: 1)положить новое значение множества PPDA равным объединению PPDA и множества {([P, Z]w(ni)[end(ni),ni], [Ьед(п2),П1]и(п2)[еп(1(п2, Z]) [P, Z] G VPDA; (ni, П2) G P; бед(тп) = P}; 2)добавить в VPDA вершины дуг, образующих пары из PPDA. Шаг 3. Положить M(D) равным семерке (Vи{/}, X, Left(P)U{Z0}, Z0, {(p1,a1, Z) (qi,ZX), (P2,a2,X) (q2, Л) ([pi,Z]ai[qi ,X], [p2, X]a2[q2, Z ]) G PPDA}U {(P, Л,Zo) (f,Zo)P G F},Po, {/}). Положить APDA(PaQ) равным (P, a, Q) для P, Q G VPDA, a G X и{Л}, PaQ G Le/t(PPDA) U Right(PPDA). Термин "маршрут", введенный при построении графа магазинного автомата, будем применять и в случае произвольного Dграфа (X, V, P, A, P0, F), т.е. будем использовать слово "маршрут"как сокращение оборота "путь, который являет ся фрагментом некоторой цепочки Dязыка LP". Будем называть нейтральным маршрут, который является цепочкой Dязыка LP. Это уменьшит насыщенность текста формулами. Слово "нейтральный"напоминает о "заряженности"маршрутов магазинного автомата. Нейтральный маршрут магазинного автомата имеет пустой заряд и является основой вычислений, которые не стирают никакую часть исходного содержимого магазина, но обязательно стирают собственные записи в магазине, т.е., в конце концов, ничего к нему не добавляют. Нетрудно заметить, что маршруты графа G(D) отличаются от маршрутов графа D только тем, что каждая их вершина содержит дополнительно некоторый символ магазинного алфавита автомата M(D). Символ, отвечающий конечной вершине маршрута T графа D, где beg(T) = P0, можно охарактеризовать следующим об -разом: если T нейтрален, это Z0, иначе это последняя из его дуг, для которых T не содержит парной дуги. Утверждение 1. L(M(D)) = L(G(D)) = L(D). Доказательство. Естественно считать, что запись TiPT2, где end(Ti) = P = beg(T2), обозначает тот же путь, что и запись TiT2. Используем это соглашение уже в определении следующей функции, помогающей описать соответствие предложе ний графов D и G(D). Функция Ф(Т, Z), где T - нейтральный маршрут графа D, Z G {Z0}ULe/t(P), определяется следующими рекуррентными соотношениями: 1)если маршрут T пуст, то Ф(Т, Z) = [P,Z], где P - вершина маршрута T; 2)если T = niTin2T2, где Ti и T2 нейтральны, (ni,n2) G P, то Ф(Т, Z) = i*(Ti,ni)2*(T2,Z), ipi = [beg(ni),Z]u(ni)[end(ni),ni], Ф2 = [beg(n2),ni]w(n2)[end(n2), Z]. Сопоставляя данное определение с алгоритмом 2, видим, что значение функции имеет форму маршрута графа G(D), но, возможно, таковым не является, так как пары [beg(ni),Z ], [end(n2),Z ] не обязаны входить в VPDA, а образование ([beg(ni), Z]u(ni)[end(ni),ni], [beg(n2),ni]u(n2)[end(n2), Z]) не обязано входить в PPDA. Пусть ExtP обозначает следующее расширение множества PPDA: ExtP = {([pi, Z]aiQi,Q2a2[p2, Z])\3X E {Zo} U Left(P) ([pi,X]aiQi,Q2a2[p2,X]) EPPDA}. Тогда ясно, что значение функции однозначно определяет некоторую цепочку x Dязыка CExtp, который содержит в себе Dязык LPPDA и, следовательно, его подмножество Sentences(G(D)). Существенно, что цепочка x либо является нейтральным маршрутом графа G(D)), либо отличается от такового лишь магазинным символом в конечных вершинах его нейтральных начальных участков. Легко доказать индукцией по k > 0, что началу цепочки 4t(T, Z), которое имеет длину 2k и принадлежит Dязыку LExtP, отвечает конечная "вершина" [end(T), Z] E V х ({Zo} U Left(P)). Учитывая конструкцию Dграфа G(D)), получаем отсюда равенство Sentences(G(D)) = {4>(T, Z0)\T E Sentences(D)}. Значит, L(G(D)) = L(D). Следующее равенство вытекает из построения автомата M(D): Sentences(Graph(M(D))) = {TiT2\Ti E Sentences(G(D)); T2 отвечает ко -манде с пустым следом, переводящей автомат M(D) в заключительное состояние f; luT) = Л}. Следовательно, L(M(D)) = L(D) □ Пример 7. Построим с помощью алгоритма 2 магазинный автомат M(Di), эк -вивалентный Dграфу Di, определенному в примере 5. Выпишем его команды в порядке построения определяющих их дуг графа G(Di): (P,a,Zo) (P,Zo PaP), (P, b, PaP) (Q, Л), (Q, b, PaP) (Q, Л), (P, a, PaP) (P, PaP PaP), (Q, A,Zo) - (f,Zo). Данный пример показывает необходимость особого заключительного состояния f E V (см. алгоритм 2) и команд вида (Q, A,Zo) - (f,Zo), не отвечающих никакой паре из PPDA. При попытке сделать заключитель ным какое либо из состояний, служивших вершинами исходного D графа, вместо M(Di) получается автомат, допускающий префиксы цепочек рассматриваемого языка, ему не принадлежащие. Заметим, что в статьях и монографиях, в которых строится пример магазинного автомата для языка {anbnn > 1}, используется именно такой принцип организации автомата, какой наблюдается в случае автомата M(Di). Автомат является детерминированным и работает в реальном времени, пока цепочка языка не прочитана. Первая половина входной цепочки целиком поступает в магазин в той или иной кодировке. 1.3. Ядро Эграфа 1.3.1. Определение ядра. В определении ядра Dграфа большую роль играет следующее понятие цикла, несколько суженное по сравнению с употребляемым в теории графов. Пусть T - непустой маршрут и beg(T) = end(T). Тогда назовем маршрут T циклом. Таким образом, циклом здесь будет называться только такой циклический путь, который является маршрутом. Понятия гнезда и парных участков, определенные в терминах магазинных ав томатов, будем употреблять для произвольных Dграфов. Ясно, что для переноса этих определений на общий случай достаточно заменить требование пустоты зарядов некоторых маршрутов на требование нейтральности этих маршрутов. Пусть T - нейтральный маршрут Dграфа D, w и d - положительные целые. Пусть T удовлетворяет следующим условиям: если Ti,... , Tm - такие нейтраль -ные циклы, что цикл Ti... Tm является участком маршрута T, то m < w; если Tii,..., Tim, T21, T31, ..., T3m таковы, что T2(i+i) = TuT2iT3i, 1 < i < m, есть гнез -до маршрута T, образованное циклами Tii и T3i, то m < d. Тогда назовем T (w,d)-каноном Dграфа D. Множество (w, d)канонов графа D назовем (w, d)-ядром графа и обозначим через Core(D,w,d). Ради краткости пишем далее "канон", "ядро"и " C or e(D)"вместо "(w, d)канон", " )ядро"и " Core(D, w, d)"соответственно. Так как нейтральный маршрут является цепочкой D языка над алфавитом дуг, можно говорить о ширине и глубине нейтрального маршрута. Для получения верхних оценок ширины и глубины канона полезно Утверждение 2. Пусть k, m и n - натуральные числа и k > (n - 1)m. Кортеж k натуральных чисел, не превосходящих m, содержит не менее n одина -ковых чисел. Доказательство. Пусть число 1 < i < m входит в рассматриваемую последова -тельность ki > 0 раз. Тогда длина последовательности есть m=i h. Предположим, что для любого целого 1 < i < m верно неравенство kj < n. Тогда ki < (n - 1)m < nm. Однако длина последовательности равна nm □ Лемма 3. Пусть m есть число вершин Dграфа D. Ширина и глубина канона графа D ограничены числами (w + 1)m и (d + 1)m2 соответственно. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||