|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[9] Доказательство. Предположим, что T является каноном, но width(T) = s > (w + 1)m. Из определения ширины следует, что T содержит участок T1 ...Ts, в котором маршрут Tj, i = 1,..., s, непуст и нейтрален. Вследствие утверждения 2 неравенство s > (w + 1)m означает, что среди начальных вершин этих маршрутов по крайней мере w + 2 одинаковы. Пусть, например, beg(Tij) = beg(Tij+1), где 1 < ij < s и 1 < j < w + 2. Тогда w + 1 участков Tij ... Tij+1 1 являются нейтральными циклами. Следовательно, T не удовлетворяет первому условию определения канона вопреки допущению, что T есть канон. Предположим теперь, что T - канон, но depth(T) = k> (d + 1)m2. Из определения глубины следует, что T содержит участок T11 . . . T1kT2k ... T21, в котором T1i и T2i, i = 1,..., k, парны друг другу. Из неравенства k > (d + 1)m2 имеем существование таких номеров ij, что beg(T1ij) = beg(T1ij+1) и end(T2ij) = end(T2ij+1) для 1 < j < d + 2. Тогда T1ij . . . T1(ij+1 1) и T2(ij+1 1) . . . T2ij являются парными в T циклами для 1 < j < d + 1. Следовательно, T не удовле творяет второму условию определения канона, вопреки допущению, что T есть канон □ Из теоремы 1 и леммы 3 вытекает Теорема 3. Пусть m есть число вершин Dграфа D. Длина канона графа D ограничена числом g(w+1)m,{d+1)m2. Следовательно, множество Core(D) конечно □ Пример 8. Пусть M - магазинный автомат из примера 6, D2 = Graph(M). Тогда пересечение множеств Core(D2, 1, 1) и Sentences(D2) совпадает с {12k234k678(98)1k, I = 0,1} U {1578(98)г/ = 0,1}. 1.3.2. Теорема о развитии. Покажем, что ядро Dграфа D выражает закон образования цепочек языка L(D) из некоторых подцепочек пометок маршрутов, входящих в ядро. Для этого определим форманты - важный "материал строи тельства"произвольных маршрутов Dграфа из присутствующих в ядре. Определяемое здесь же бинарное отношение развития на множестве маршрутов можно расценить как "инструмент строительства". Основная здесь теорема 4 имеет ана -логию с классической теоремой о разрастании цепочек бесконтекстных языков. Пусть (T1,T2,T3) есть гнездо, в котором T1 и T3 - циклы. Пусть (T12, T2, T32) и (T11, T12T2T32, T31) не являются гнездами в маршруте T1T2T3 для любых циклов T11, T12, T32, T31, таких, что T1 = T11T12, T3 = T32T31. Тогда назовем гнездо (T1,T2,T3) простым. Пусть маршрут T является нейтральным циклом или простым гнездом и не содержит меньшего участка, который есть нейтральный цикл или простое гнездо. Тогда назовем маршрут T формантом. Определим бинарные отношения D, TD на множестве маршрутов Эграфа D: (T, T) eD (с историей (T1,T2, T3, T4, T5)) тогда и только тогда, когда T = TlT3T5, T = TlT2T3T4T5, T2T3T4 есть формант, в котором T2 и T4 являются парными циклами; (T,T) eD (с историей (Tl,T2,end(T2),end(T2),T5)) тогда и только тогда, когда T = TlT2T5, T = T{T5, T2 есть циклический формант. Объединение ffD=\D U TD будем называть отношением развития. Пусть T, T - это маршруты графа D. Пусть либо T = T, либо для некоторого k > 0 существует последовательность gen(T) = ((T11,T12,T13,T14,T15), , (Tkl ,Tk2,Tk3,Tk4,Tk5)), такая, что V = ТцТ, T = TklTk2TT, (TTuTT) e Ь с историей (Tn,Ti2,Ti3,Ti4,Ti5) и (T(i-l)lT(i-l)2T(i-l)3T(i-l)4T(i-l)5, TilTi2Ti3Ti4Ti5) ei[D с историей (Til, Ti2, Ti3,Ti4, Ti5), 1 < i < k. Тогда назовем последовательность gen(T) родословной (с предком T) маршрута T; число k назовем длиной родословной. Если T = T, то родословная маршрута T (с предком V) пуста. Отметим, что маршрут может иметь несколько родословных даже при одном и том же предке и одной и той же длине родословных. Пусть маршрут T содержит нейтральный цикл или парные циклы. Тогда на зовем маршрут T производным. Маршрут, не являющийся производным, назовем элементарным. Теперь установим, что среди предков каждого нейтрального маршрута есть канон (более того, элементарный канон). Лемма 4. Каждый производный маршрут содержит в себе формант. Доказательство. Ясно, что каждый производный маршрут содержит производный нейтральный участок. Выберем среди нейтральных производных участков производного маршрута минимальный по длине. Предположим, что выбранный участок T не является формантом. Тогда из определения форманта следует, что T содержит меньший участок, который является нейтральным циклом или гнездом, образованным парными циклами. Итак, исходный маршрут содержит производный участок, который короче, чем T, вопреки выбору T □ Определим две функции, отображающие маршруты в множества маршрутов. Пусть T - маршрут. Пусть Sl = {TlT3 3 (нейтральный цикл T2) T = TlT2T3}, S2 = {TiT3T5 3 (циклы T2,T4) (T2,T3,T4) является гнездом в T = T3T4T5} DelCycle(T) = { {T} Sl = 0 * 1 Sl иначе. DelPair(T) = ( {J} S2 = 0 S2 иначе. Следующие функции отображают некоторые разбиения маршрутов во множества маршрутов. Пусть TTT- маршрут. Пусть S3 = {TiT3T5 е DelPair(TTT") 3 (T2, T4, T[, T5) (T = TT2T, T" = T5T4T5, T3 = T{TT5) }. PreservingDel(T,T,T) = I {TTT"} S 0 v 1 S3 иначе. Пусть m > 1, T = TiT/ ... Tm iTlm iTm - маршрут. Пусть S обозначает объединение следующих двух множеств: {TiTi... Ti i T! iTiT ... Tm iTm iTm 1 < i < m "Ti е DelCycle(Ti) U DelPair(Ti)}, {TiTi... Ti i T i TiT... Tj i T i T Tj ... Tm i Tm i Tm1 < i<j < m, T{T[ ... Tj i Tj i T е PreservingDel(Ti, Ti ... Tj i Tj i ,Tj)}. Если S = 0, то значением reduction(Ti, T[, ..Tm i, Tm i, Tm) является множество {T}, иначе множество UfiT{ ...fm-1Trn 1fm&Sreduction{Ti, Ti, . . . , Tm i , Tm i , Tm). Лемма 5. Пусть T - нейтральный маршрут; пусть (T,T) efr> с историей (T, T2, T3, T4, T5). Тогда существует (2,1)канон Tl ГТ1 ГТ1 ГТ1 ГТ1 ГТ1 0 = T0i T2T3T4T05, такой, что pair(T0) = pair(T). Доказательство. Пусть T0 = T0 iT2T3T4T05 е reduction(Ti,T2T3T4,T5). Убедимся, что T0 является (2,1)каноном. Из построения маршрута T0 следует, что каждый его нейтральный цикл должен иметь общий участок с формантом T2T3T4. Следовательно, для участка T . . . T m маршрута T0, в котором T i явля ется нейтральным циклом для i = 1,... ,m, число m не может превышать двух. Из построения маршрута T0 следует также, что хотя бы один из парных в нем циклов должен иметь общий участок с формантом T2T3T4. Следовательно, гнездо T = T2T3T4 маршрута T0, которое отлично от T2T3T4 и в котором T2 и T4 -парные циклы, содержит в себе формант T2T3T4. Если T2T3T4 содержится в одном из циклов T2, T4, то гнездо T является простым. Если T2T3T4 имеет общий участок с каждым из циклов T22, T4, то pair(T3) = pair(T33) (иначе маршрут T2T3T4 не был бы формантом). Следовательно, и в этом случае гнездо T = T2T3T4 является простым. Таким образом, T0 удовлетворяет определению (2,1)канона □ Прием применения функции reduction подходит и в доказательстве следую щего факта, который влечет возможность построения D множества магазинного автомата за конечное число шагов. Лемма 6. Пусть (ni,T2,n2) есть гнездо некоторого предложения TniT2n2T3, ni и п2 являются дугами. Тогда существуют такие маршруты Ti, T22, T3, что TiniT2n2T3 является предложением и (1,1)каноном, а (ni,T22,п2) - его гнездом. |
Среды: 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 | ||