|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[11] Доказательство. Легко видеть, что каждый непустой успешный маршрут удовлетворяет определению цепочки, входящей в R. Пусть T Е Lp П R. Тогда по лемме 9 T является нейтральным маршрутом. Так как из соотношения T Е R следуют соотношения first(T) Е A и last(T) Е B, нейтральный маршрут T успешен □ Теорема 6 (о морфическом представлении бесконтекстного языка). Пусть L С Е* - бесконтекстный язык. Тогда существуют такие Dязык L, локальный язык R и хороший (отображающий символ в символ или пустую цепочку [Eilenberg 74]) морфизм h, что L = h(Ln R). Доказательство. Так как L - бесконтекстный язык, он определяется некото рым Dграфом D. Используя множество дуг Dграфа D в качестве алфавита, определим локальный язык R, как в начале параграфа. Определим морфизм h : E* - Е* формулой h(n) = со(тт), п Е E. По теореме 5 множество успешных маршрутов совпадает с Lp П R. Так как определяемый D графом язык есть множество пометок всех его успешных маршрутов, верна формула L = h(LP П R) □ Следствие 1 (теорема ХомскогоШютценберже). Пусть L С Е* - бесконтекстный язык. Тогда существуют такие язык Дика L, локальный язык R и хороший морфизм h, что L = h(L П R). Доказательство. Пусть LP - это язык Дика над некоторым Dмножеством р С Е( х Е), удовлетворяющим равенствам Е( = Е) = р = Пусть А = Е( U Е) и ф : P - p есть некоторая биекция. Можно сказать, что функция ф снабжает уникальным обозначением каждое вхождение в элементы Dмножества P скобок из E = Left(P) U Right(P). Из определения функции ф следует сюръективность функции С : А - E, заданной соотношениями (из равенств Е( = Е) = следует, что каждый символ алфавита А входит в некоторую пару из D множества р): У (a, b) Е р С (a) = a, С (b) = b, ф(а, Ь) = (a, b). Здесь возможно равенство С(ci) = С(с2) при c\ = c2. Отметим, что функция С индуцирует побуквенный (отображающий символ одного алфавита в символ другого [Salomaa 81]) морфизм С : А* - E*. Из определения функции ф следует биективность функции Ф : Lp - Lp определяемой соотношениями Ф(Л) = {Л}, Ф(п1Тп2) = аФ(Т)Ь, Т eLv, (тг1,7Г2) eV, (а,Ь) = ф(т ,п2), Ф(тгт2) = Ф(Т1)Ф(Т2), Ti,T2 e Lp. Для произвольной подцепочки Т цепочки из Lp обозначим через Ф(Т) множество {ж2(ЭТ1,Т2,Тз) (Т2 = Т, Т1Т2Т3 e Lp, ФСТ1Т2Т3) = Ж1Ж2Ж3, Ti = \xi\ для i = 1, 2, 3)}. A = J Ф(п), B = U Ф(п), С = А2 - U Ф(П1П2). R = (ЛА* П А*В) - А*СА* является локальным языком, а {Ф(Т)Т является успешным маршрутом Dграфа D} = LP П R. Теперь видна справедливость равенства L(D) = h(Z(Lp П R)), где h - морфизм, определенный в доказательстве теоремы 6. Так как композиция морфизмов есть морфизм и ( - морфизм побуквенный, h = h( : А* - X* является хорошим морфизмом. Построенные язык Дика LP, локальное множество R и хороший морфизм h позволяют вывести из теоремы 6 справедливость рассматриваемого утверждения □ §3. Одно обобщение регулярных выражений В данном параграфе определяются и изучаются КСвыражения - обобщение регулярных выражений. Название отражает тот факт, что КСвыражения характеризуют бесконтекстные языки, или КС языки. Вводится система понятий, кото рая служит инструментом исследования КС выражений и отвечающих им языков. Эта система используется в данной статье для доказательства следующих двух фактов: 1)Dграфы и КСвыражения характеризуют один и тот же класс языков; 2)класс так называемых псевдосогласующих КСвыражений эквивалентен классу регулярных выражений. Отметим возможность несколькими способами доказывать, что КСвыражения характеризуют бесконтекстные языки. Первый из упомянутых выше фактов при мечателен как обобщение теоремы Клини. Выделяется обширный подкласс КС выражений, характеризующий регулярные языки. Настоящий параграф следует считать продолжением параграфа 1, материал ко торого существенно здесь используется. В целом он представляет полученные к данному моменту результаты наших исследований по выявлению и адекватному выражению общей сути различных характеризаций бесконтекстных языков. В пользу таких поисков можно заметить следующее. С помощью понятия синтаксической конгруэнции [Lallement 79] регулярный язык можно представить системой компонентов, не зависящей от тех или иных способов его задания, приписывающих его цепочкам некоторую структуру. При этом существует определенная взаимосвязь между компонентами упомянутой системы и любым из возможных синтаксисов регулярного языка (подразумеваются синтаксические описания, изу чаемые в рамках теории регулярных языков). Именно наличие такой связи обеспечивает возможность отвечать на все вопросы о конечных автоматах. Есть основания полагать, что некоторое обобщение известных результатов позволит раскладывать на компоненты детерминированные языки (а может быть, и бесконтекстные языки некоторых более общих классов) таким образом, чтобы это помогало отвечать на вопросы о соответствующих автоматах и грамматиках. В связи с этим ясно, что разложение устройств, задающих бесконтекстные языки, на некоторые компоненты помогает нащупать способ обобщения приемов, разра ботанных для более узких классов языков. При разработке обобщения регулярных выражений мы руководствовались сле дующими соображениями. Звездочка Клини качественно отличается от других регулярных операций. Ее смысл позволяет интерпретировать регулярное выраже ние а, задающее бесконечный язык, как описание формальной системы, теоремы которой фиксируют "синтаксический разбор относительно а"отдельных цепочек языка. Для обоснования этого тезиса обсудим регулярные выражения над неко -торым алфавитом Е. Язык, заданный регулярным выражением а, обозначим через L(a). Заметим, что в записи регулярного выражения а над алфавитом Е "рассре -доточены"цепочки, составляющие некоторое конечное подмножество L(a) языка L(a); L(a) можно определить рекурсивно: L(0) = 0, L(a) = {а} для a G Е U {б}, L(a) = L(e) U L(y) для а = в + 7, L(a) = L(e)L(7) для а = (e)(7), L) = {Л} U L(e) для а = (в)*. Теперь возьмем в качестве аксиомы само выражение а, а в качестве правила вывода удвоение вхождения подвыражения вида (7)*, т.е. посылке вида x(7 )* У, где 7 - регулярное выражение и xy - регулярное выражение или пустая цепочка, отвечает заключение x(7 )*(7 )*y- Ясно, что l) = у L(e). в выводится из а Мы задались целью обобщить правило вывода рассмотренной выше системы, учитывая закон образования цепочек нерегулярного бесконтекстного языка, ука занный вариантами теоремы о развитии [Станевичене 96б], [Станевичене 99] (в |
Среды: 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 | ||