Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[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 графов), чего нельзя сказать о других известных выражениях для задания этих



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49]