|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[1] что техника анализа поведения магазинного автомата, потребная при рассмотрении проблем эквивалентности и регулярности в классе детерминированных языков, в нужной мере разработана: опубликована не одна работа по указанной теме, не имеющая необходимого уровня строгости и ясности и даже ошибочная. В свете сказанного актуальным является поиск таких характеризаций бесконтекстных языков, которые дали бы понятийную среду, удобную для выражения и исследования явлений, связанных с трудными задачами теории бесконтекстных языков. Одна из целей настоящей работы как раз и состоит в создании характеризации бесконтекстных языков, наиболее удобной для развития их теории. В огромном богатстве наблюдений, накопленных в теории формальных языков и в прикладных работах, не могли отсутствовать указания, которые, впрочем, стали для нас заметны только тогда, когда цель и средства ее достижения в основном оформи лись. Начальный этап работы был подготовлен нашим участием в разработке и реализации языков программирования, которое отражено в работах [Гончарова 71], [Гончарова 72], [Гончарова -Станевичюс 71] и других, определенным образом подытоженных в [Бурова -Станевичене -Станевичюс -Шкляр 83]. Эти занятия пробудили большой интерес к упоминавшимся выше методам синтаксического анализа, поддержанный С.С.Лавровым. Именно наблюдение специфики детерми -нированных магазинных автоматов, скрытых за LR(1) таблицами, вселило уве ренность в возможность создания наиболее плодотворного инструмента анализа магазинных автоматов и бесконтекстных языков. Здесь мы даем не полный обзор результатов, которые можно назвать подго -товляющими нашу работу, а скорее историю (также не полную) наших встреч с подсказками и подтверждениями правильности выбранного пути. Одна из первых наших идей - получить графы, которые эквивалентны магазин -ным автоматам и естественным образом обобщают то, что теперь называют иногда просто конечными автоматами [Salomaa 81], [Eilenberg 74] (в начальный пери -од формирования терминологии бытовали более громоздкие обороты, например, "граф для диаграммы состояний (строго конечного) автомата"[Chomsky 63]). Та -кие графы давали бы зримый образ вычислений магазинного автомата во всех их деталях, заставили бы понятия теории графов больше работать в задачах теории формальных языков. Была и некоторая надежда (очень слабая, так как привлече ние магазина вносит, очевидно, новое качество), что графическое представление магазинных автоматов поможет естестенным образом обобщить на бесконтекст ный случай какие либо достижения теории регулярных языков. Надежда эта не была совершенно лишена основания: можно заметить, насколько родственны по приемам доказательства теорема о представлении регулярного языка морфиче ским образом локального языка [Salomaa 81] и теорема 6 главы 1 данной работы. Следует также отметить, что в параграфе 4 главы 3 продемонстрирована воз можность привлечения приемов, использованных, например, в [Eilenberg 74] для изучения конечных автоматов, для исследования графов магазинных автоматов реального времени с одним поворотом. Нечто похожее на наш подход можно найти и у других исследователей (см., например, "подход диаграмм состояний для магазинных автоматов"в [Salomaa Wood -Yu 94]). Но применение этих разработок обычно невелико; иногда оно ограничивается новыми доказательствами леммы Огдена. Для обеспечения стандартности и лаконичности информации, определяющей дугу графа магазинного автомата, требовалась некоторая нормальная форма автомата. Была использована форма, характеризуемая следующей дисциплиной работы с магазином: 1) каждый такт или добавляет в магазин ровно один символ, или стирает, также ровно один символ, никогда не стирая исходного содержимого магазина - так называемого маркера дна; 2) к концу чтения допускаемой автоматом цепочки он стирает все, что записывал, при этом магазин не опусто шается: в нем остается маркер дна. Черты данной формы магазинного автомата можно найти в большом числе работ. Наиболее близка нашей форма, рассмотренная А.В.Гладким; да и техника протоколов (о них см. в [Гладкий 65а], [Гладкий 73]) ассоциируется с нашим понятием маршрута на графе магазинного автомата. Поиск подходящей формы магазинного автомата явился и поиском уравновешенности двух средств запоминания информации о допускаемых цепочках: со стояний и магазина, одинаковой востребованности их во всех конфигурациях, возникающих при обработке правильной входной цепочки. Ненормальны, напри мер, такие записи в магазине, которые станут "мусором"в заключительной кон фигурации. Вряд ли нормально и опустошение изначально непустого магазина, в результате чего автомат "выключается". Аккуратное соответствие записей в магазин и стираний, кажущееся необходи мым (оно, конечно, не достаточно) в удачно построенном магазинном автомате, живо напоминает о скобках. С другой стороны, парные скобки - это лишь модель парных символов и даже цепочек, присутствие которых отличает бесконтекстные языки, не являющиеся регулярными. Понятия скобки и скобочной системы формализованы с помощью языков Дика, самые полные сведения о которых среди легко доступных нам источников содер жит книга [Lallement 79]. Алгебраическая интерпретация языков Дика побудила нас подняться немного над теорией магазинных автоматов и построить обобще ние ограниченных языков Дика [Lallement 79], более точно отражающее характер объектов, парных в цепочках бесконтекстных языков. Далее будем называть огра -ниченные языки Дика просто языками Дика, следуя традиции, сложившейся в работах по теории формальных языков. Название "D языки"предлагаемого обобщения языков Дика сохраняет в себе первую букву словосочетания "Dyck languages". Данная работа базируется на систематическом использовании понятия D языка. В нашем обобщении пара скобок - это пара символов, как и в случае языков Дика. По прежнему, множества открывающих и закрывающих скобок не пересе каются. Но теперь в различных парах открывающие или закрывающие элементы могут совпадать. Случай парных цепочек, длина хотя бы одной из которых не рав на единице, не отражен здесь непосредственно. Однако вычисления магазинных автоматов, "аккуратно"использующих магазин, имеют теперь полную аналогию со скобочными системами. В данной работе введены термины для определенных фрагментов скобочных систем. Формализованы представления о глубине и ширине - числе последова -тельно сцепленных скобочных подсистем. Доказана конечность числа скобочных систем с ограниченными глубиной и шириной. Все это способствовало строгости, ясности и краткости в изложении наших результатов. Подобную "теорию скобочных систем", связанную с языками Дика, мы обнаружили в [Ehrenfeucht -Hoogeboom -Rozenberg 86]. Однако важность понятия скобки отмечалась во многих работах, в том числе прикладных. Очень убедительно писал о роли скобок Леви [Levy 75]. Отметим, что работа [Levy 75] стимулировала ряд исследований на тему нейтрализации синтаксических ошибок. В одной из работ этого ряда сделана попытка обобщить понятие скобки [Ciesinger В работе [Ehrenfeucht Hoogeboom Rozenberg 86] подчеркивается полезность изучения комбинаторных свойств скобочных систем, буквально: We formulate and prove a number of combinatorial properties of Dyck words ... Since Dyck words are used in the investigation of various types of data structures, these results seem to be of independent (combinatorial) interest. В ней, в частности, определяются понятия глубины и ширины цепочки языка Дика и выводится верхняя оценка длины цепочки через ее глубину и ширину. Она того же порядка, что и наша. С помощью указанных результатов работа [Ehrenfeucht Hoogeboom Rozenberg 86] изучает представление магазинного автомата парой согласованно применяемых грамматик. Грамматики порождают: одна - читаемые автоматом входные цепочки, другая - соответствующие магазинные цепочки. Последняя грамматика не вполне традиционна: она не различает терминальных и нетерминальных символов. Определение графа магазинного автомата и связанная с ним система понятий опубликованы в [Станевичене 83], [Станевичене 84], [Станевичене 87а], [Станевичене -Мельников 88], [Станевичене 89], [Кузнецова -Ожиганов -Сагинтаева -Станевичене 90], [Станевичене 93а], [Станевичене -Вылиток 93], [Stanevichene 94], [Вылиток -Станевичене -Чернцов 96] и [Станевичене 99]. Но терминологию можно считать сложившейся только в двух последних работах. В них впервые дана характеризация бесконтекстных языков D графами. В системе понятий, основанной на нашей графической интерпретации бескон текстных языков, понятие ядра является, возможно, главнейшим. Понятие цик лического пути вместе с понятием скобочной системы помогло нам осмыслить, что некоторое конечное подмножество путей на D графе (аналогично, некоторое конечное подмножество сентенциальных форм бесконтекстной грамматики) вы ражает закон образования цепочек языка из подцепочек той его части, которая определяется выделенным подмножеством - ядром. Упомянутый закон, повидимому, проще всего объяснить как закон получения цепочек, отвечающий так называемым КС выражениям, которые определяются в главе 1. В этом определении вместо регулярной операции итерации рассматри-вается новая операция - именование. Эффект операции именования определен с помощью понятия скобки. На наш взгляд, в понятии КС выражения концен трируются общие черты изучаемых в данной работе формализмов для описания бесконтекстных языков (магазинных автоматов, бесконтекстных грамматик, D графов), чего нельзя сказать о других известных выражениях для задания этих |
Среды: 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 | ||