Расширение класса индексных языков тема диссертации и автореферата по ВАК РФ 01.01.10, кандидат физико-математических наук Маслов, Александр Николаевич

• Маслов, Александр Николаевич
• кандидат физико-математических наук
• 1981

Введение диссертации (часть автореферата) на тему «Расширение класса индексных языков»

Задача формального языка, будь то естественный язык, например русский, или язык программирования, например Алгол 60, состоит в построении конечного представления для потенциально бесконечного класса предложений языка* Наиболее естественным подходом к описанию языка является построение порождающей грамматики, Другой подход связан с построением распознающего автомата.

Классическим типом порождающих грамматик считаются бесконтекстные грамматики [1] . Однако для ряда приложений и теоретик ческих исследований класс бесконтекстных грамматик является недостаточным* Поэтому в течении ряда лет значительное внимание уделяется изучению более широких классов рекурсивных языков [5, 12, 26, 27 ].

Целью настоящей работы является определение и исследование нового типа грамматик, называемых многоуровневыми индексными грамматиками. Показывается, что многоуровневые индексные грамматики обладают многими свойствами бесконтекстных грамматик, обеспечившими их практическую применимость, и являются существенным расширением последних. Рассматривается также соотношение многоуровневых индексных грамматик и грамматик Вейнгаардена, использованных для описания языка Алгол 68.

Актуальность темы обусловлена трудностями при формальном описании современных языков программирования и необходимостью совершенствовать методы трансляции, а также расширением сферы применения формальных грамматик в других областях (теория развивающихся организмов [36] , схемы программ, логический вывод).

Предшествующее работы.

Активное развитие теория формальных грамматик начала после работы Хомского [I] , где вводится класс бесконтекстных грамматик в качестве модели для формализации синтаксиса фрашентов естественных языков. К настоящему моменту теория бесконтекстных грамматик хорошо разработана во многих направлениях [2, 3, 4, 21» 22] ; в ней получено много интересных и содержательных результатов. Установление эквивалентности бесконтекстных грамматик и магазинных автоматов явилось основанием для использования бесконтекстных грамматик для описания, реализации и исследования языков программирования* При этом магазинный автомат составлял основу синтаксической части транслятора* Бесконтекстные грамматики были удачно использованы для описания синтаксиса Алгола 60« Класс бесконтекстных грамматик мы обозначим

При дальнейшем развитии языков программирования выяснилось, что беоконтекстиых грамматик недостаточно для описания ряда конструкций* Так для описания Алгола 68 были введены грамматики Вейнгаардена (обозначаемые далее через V/" ), позволяющие добиться некоторой наглядности при описании языка. Примерно в то же время в работах А.х©[7, 3] были введены и изучены индексные грамматики (в наших обозначениях класс а в диссертации М* Фишера [э] были определены два класса грамматик 10 и 01, обобщающие известные тищ! макрогенераторов* Класс 01 грамматик оказался по порождающей способности эквивалентным классу индексных грамматик» Ахо показал, что индексные грамматики обладает основными из тех свойств бесконтекстных грамматик, которые делают их удобными для описания фрагментов естественных языков и языков программирования, а также определил для них класс допускающих автоматов.

Дальнейшие результаты, касающиеся индексных грамматик, получены в [9, 10, 18, 19] , см. также обзоры [б] и [12^ В [18] Ш. Грейбах обобщила метод построения допускающих автоматов для индексных грамматик.

Синцов [13] показал, что грамматики Вейнгаардена по-роадают все рекурсивно-перечислимые множества, поэтому невозможна система построения трансляторов на их основе (нет распознающего алгоритма). Этим в определенной мере обусловлена сложность реализации Алгола 68 (см. £371 ). у

Метод описания языка программирования (или фрагмента естественного языка в системе автоматического перевода) должен удовлетворять двум противоположным требованиям, первое, он должен позволять описывать как можно больше языков. Второе, для описанных языков должен иметься (достаточно простой) алгоритм анализа. 1 этом отношении введение индексных грамматик [?] и автоматов, допускающих индексные яжыки [в] , является существенным шагом по отношению к бесконтекстный грамматикам.

Основные результаты.

В настоящей диссертации рассматривается возможность дальнейшего расширения класса индексных языков.

Определяется последовательность Як классов языков, порождаемых обобщениями индексными грамматиками (классы которых также обозначаются -Йк)* Показано, что каждому классу -Ак, К < <*> соответствует семейство допускающих автоматов К (названных ^-уровневымж магазинными автоматами). Изучены свойства замкнутости классов & К . Каждый из них является полным главным абстрактным семейством языков. Показано, что при К < разрешимы проблема, пустоты и проблема прянадлежности для классов Ж ^ класс У- ос совпадает с множеством рекурсивно-перечислимых языков* Показано, что класс языков» порождаемых грамматиками Вейнгаарцена (использованными для описания Алгола 68) с однозначными понятиями содержится в классе ч&з • Следовательно» для него разрешимы проблемы пустоты и принадлежности, хотя они не разрешимы для грамматик Вейнгаардена общего вида. Определяется соответствующая последовательность макрограмматик»

Б § I (опубликовано в [152 предложено некоторое изменение (по отношение к использованным в £7] ) обозначений в опрестале- „ делении индексной грамматики* Благодаря этому изменению >^естес-твенным образом расширить класс индексных грамматик» осуществляя переход от к Л ктак же, как он осуществляется от бесконтекстных ( ) к индексным ( ЗЦ' )♦ ?еорема 4 из § 2 показывает» что тем же способом можно осуществить переход от конечноавтоматных (которые можно обозначить о ) языков к бесконтекстным 51 , и является еще одним обоснованием пропорции Раунд с а [ю] : "класс конечноавтоматных языков так относится к классу бесконтекстных языков, как класс бесконтекстных языков к классу индексных языков". А.А, Мучник при обсуждении работы [ю] на семинаре по теории языков и автоматов в МГУ предположил, что эта пропорция может быть продолжена* Введенная последовательность классов языков ,9-к является непосредственным продолжением пропорции Рауцдса.

В § 2 изложены основные свойства классов Як! разреши* мость проблем пустоты и принадлежности при °° * равенство классов языков рекурсивно-перечислимых V построение приведенной формы для индексных грамматик*

Грамматики Вейнгаардена порождают все рекурсивно-пере-числимые множества» поэтому невозможна система построения трансляторов на их основе (нет распознающего алгоритма). Г.С. Цейтин в беседе с автором высказал предположение, что можно ввделить (достаточно широкий) подкласс грамматик Вейнгаардена с разрешимой проблемой принадлежности, В теореме 5 из § 3 (опубликовано в [14] ) показано* что таким подклассом Является класс грамматик Венгаардена с однозначными понятиями» т.к. он вложен в класс •

При введнных обозначениях переход для К < ®о от классов обобщенных индексных грамматик, порождающих классы ~ЯК * к классам ТПк допускающих автоматов производится (§4, опубликовано в [г?] ) столь же естественно, как и переход от бесконтекстных грамматик к магазинным автоматам* Сходные ков* струкции автоматов рассматривались также Грейбах [18] «

В § 5 (опубликовано в [20] ) вводится понятие системы допускающих автоматов* Показано, что каждому полному главному абстрактному семейству языков [19] соответствует система допускающих автоматов и наоборот, а также» что каждый их введенных классов автоматов 7П к является системой допускающих автоматов (т.к. можно ограничить магазинный алфавит).

В § 6 определяется последовательность макрограмматик и доказывается* что она порождает класс языков Я к .

В заключении приведены результаты относительно многоуровневых индексных языков, полученные другими авторами.

Обозначения и терминология

Языком в алфавите 2 = , -ч^} называется любое ^ множество слов из символов (Г» . Через обозначается язык, состоящий из всех слов в алфавите 2 ,а через язык, состоящий из всех слов в алфавите 5И , исключая пустое слово (обозначаемое в дальнейшем через £ ).

Над языками определены обычные теоретико-множественные и полугрупповые операции: объединение, пересечение, произведение Ц/ | 2 € Ц) , итерация ( Ц*- {б} I) 1д II , замыкание Клини (1а+= Ц 1) и2и гомоморфизм (задаваемый на символах алфавита к: 22—*Е и продолжаемый равенствами

4(е)=£; ккI к^иу-Л^и обращение гомоморфизма ( К к (я^е Ц} где IV гомоморфизм)•

Гомоморфизм к называется нестирающим, если ^(ос)^ £ при .

Минимальный класс языков, содержащий все конечные языки (т.е. языки, состоящие из конечного числа слов) и замкнутый относительно операций объединения, произведения и итерации, называется семейством регулярных языков.

Класс языков называется абстрактным семейством языков (сокращенно АСЯ) [19], если он содержит непустой язык и зам-ф кнут относительно операций объединения, произведения; итерации, нестирающего гомоморфизма, обращения гомоморфизма и пересечения с регулярными языками«

Язык всегда рассматривается в конечном алфавите, но объединение алфавитов языков из любого абстрактного семейства языков содержит все мыслимые символы.

Абстрактное семейство языков называется полным, если оно замкнуто относительно произвольных гомоморфизмов.

Полное) абстрактное семейство языков называется (полным) главным, если оно порождается одним языком с помощью операций, участвующих в определении (полного) абстрактного семейства языков.

Следует заметить, что полное главное абстрактное семейство языков может не быть главным абстрактным семейством языков (в случае, если из образующего языка без стирающего гомоморфизма все языки не порождаются).

Отношение включения обозначается символом € , отношение "быть подмножеством" символом Я , пустое множество обозначается ф • Длина слова х обозначается через 1(ос) . Декартово произведение (множество упорядоченных пар элементов множеств М, и М.) обозначается М,* М«, , а Мх.* М кДпЗ и раз обозначается г1 М я

Операции алгебры логики и кванторы обозначаются V, Л , э > ш 9 V и 3 соответственно.

Множество всех подмножеств М обозначается 2 Через <х> будем обозначать множество символов, входящих в слово сс . Через <яс4,., ос^> п >2 9 будем обозначать упорядоченное множество с элементами 0^,., ос^,

Через } будем обозначать неупорядоченное множество с элементами X. . * 7 IV

Основными способами задания языков являются порождающие грамматики и допускающие автоматы.

Все задания одного и того же языка (или одного и того же семейства языков) будем называть эквивалентными« В частности; будем говорить об эквивалентности двух грамматик и об эквивалентности класса грамматик и класса автоматов.

Порождающая грамматика (в смысле Н Доме кого) - это упорядоченная четверка , V , Р, ¿>0У где XI конечный алфавит основных символов, V - конечный алфавит вспомогательных символов; Р - множество продукций • , где V* , а фе(УиП) , - начальный символ.

Слово х^ выводимо из слова осс^ применением продукции ц/ . Вывод в грамматике начинается с и заканчивается словом из 2 * . Множество выводимых слов образует язык, порождаемый грамматикой .

Если^бУ для каждой продукции , то грамматика называется бесконтекстной. Л если еще Фб для каждой продукции <р-»>(|> , то грамматика называется регулярной.

Йзвестно[21, 22], что для каждого рекурсивно-перечислимого множества можно построить порождающую его грамматику.

Конечный автомат это пятерка ТА"* (21^У 7 где 2- конечный входной алфавит, (3 - конечное множество состояний, !Х : £( ■ б - функция переходов, ^о<£ 0 -начальное состояние; Т*1 £ (3 - множество заключительных состояний.

Автомат в начальном состоянии начинает последовательно читать входное слово, изменяя свое оостояние согласно функции переходов. Слово считается допустимым; если прочитав его автомат пришел в заключительное состояние. Автомат допуокает язык, образованный из всех допустимых автоматом слов.

Возможно использование недетерминированной функции О переходов (недетерминированный конечный автомат). Тогда автомат, прочитав символ б" в состоянии переходит в любое из состояний из . Слово считаетоя допустимым, если при одном из способов работы автомат; прочитав его, пришел в заключительное состояние. V

Известно, что конечные автоматы, конечные недетерминированные автоматы, конечные недетерминированные автоматы с одним заключительным состоянием и регулярные грамматики эквивалентны и определяют семейство регулярных языков .

Преобразователь с конечным числом состояний это конечный автомат с выходной лентой. После каждого применения функции перехода преобразователь печатает на выходной ленте слово9 зависящее только от состояния преобразователя.

Магазинный автомат (МП- автомат) - это семерка М = Т1,^ 2 - конечный входной алфавит, О - конечное множество состояний, V - конечный магазинный алфавит, £: 0. х I) {в} х Г и ] —> [множество конечных подмножеств множества 0*Г } - функция действия, 2± - маркер дна магазина, Ц - начальное состояние, 0 - множество заключительных состояний*

Помимо входной ленты (на которой записано распознаваемое слово) МП - автомат обладает вспомогательной (магазинной) лентой, на которой записаны символы из Г . Магазинную ленту будем представлять расположенной вертикально. Внизу ленты записан символ (дно магазина); а вверху последний из записанных символов (который и обозревается автоматом),

Если ЗС^б^Н) , то МП - автомат М находясь в состоянии ^ , читая входной символ 6* (2 или £ ) и обозревая символ 2 вверху магазина, может перейти в состояние , сдвинуться по входной ленте вправо (на один символ, если , или остаться на месте, если в*- £,), стереть верхний магазинный символ и записать вверху магазина символы из слова Ы .

Автомат начинает работу, обозревая самый левый символ на входной ленте, находясь в состоянии с^ и имея в магазине только символ . Затем последовательно совершаются вышеописанные шаги. Если автомат вместо символа 2 пишет £

V О на магазинную ленту; то на этом его работа заканчивается.

Допустимость слова можно определить двумя способами, приводящими к двум эквивалентным классам автоматов* При первом^ способе требуется, чтобы автомат ., прочитав входное слово, перешл в состояние из Т* , а при втором, - прочитав входное слово, опустошил магазин.

Известно [21, 22] , что класс магазинных автоматов, класс магазинных автоматов с одним состоянием (при допустимости пустым магазином) и класс бесконтекстных грамматик эквивалентные

Действия магазинного автомата существенно недетерминированные Класс детерминированных магазинных автоматов не эквивалентен клаосу магазинных автоматов, хотя с практической точки зрения наиболее интересен класс бесконтекстных грамматик, для которых можно строить эквивалентные детерминированные магазинные автоматы*

Магазином элементов из Я будем называть последовательность г • -> > е Я у причем элемент (^(независимо от расположения в пространстве) будем называть верхням*

§ I. Определение классов порождающих грамматик*

Для определения класса индексных грамматик нам потребуется операция возведения в степень на множестве языков* Обозначим через \Л= Я, В в V 3 множество всех выражений вида /) * Доопределим операцию возведения в сте пень до операции над языками с помощью равенств: Я = Я

МуЧик1;, (иуЧй> ^ ^ где Я и В символы из алфавита V , а и языки в алфавите V . Указанные равенства позволяют по интерпретации для выражений (т.е. по отображению V -»-V ) определить язык 2 для языков иА и в алфавите V ♦ Тем самым, в частности, определена операция возведения в степень для слов. В выражении Я& букву В будем называть индексом буквы Я . Теперь можно определить класс индексных языков, используя несколько более удобные обозначения, чем в[7].

Определение I [15]. Индексной грамматикой называется пятерка , где Ц= }- алфавит основных символов, У = {$0алфавит (вспомогательных символов), начальный символ; Р -конечное множество продукций вида 11\/и2) и интерпретация операции возведения в степень. Слово ^ выводимо из слова ос. применением продукции <реР (обозначается х у, ), если = —^ Со . Слова & и н - в произвольном алфавите. Слово ^ выводимо из слова ос (обозначается XI—о^), если существует последовательность слов ос = ^ такая, ЧТО либо - Лля некоторого |>€р , либо получается из заменой некоторого вхождения /1 В на 1(ЯВ) . Каждая грамматика определяет язык 1*((][)*{х€ ¿0 «— ос) выводимых в ней слов« Отме

Я л с , I тим, что выражения 6 и Я , являются тупиками т.е. из них нельзя ничего вывести).

Определение выводимости в индексной грамматике допусу ^ кает естественное расширение. Пусть У((0 = [Я*МУ(Ы)}* И У(оо)= и Ч(к). Например, Я вефСЪ7е У(5) И Я^'""1^ У (к), слово ^ выводимо из слова ос применением правила реР на уров

Р к не (обозначается ос Ч)» если существуют слова &0 и из и из ус«.) такие, что эс= «0, ^ = а0¿¿' И„, 2. = &. £ .м ,

V V при р: • Будем отождествлять выводимость — и выводимость I . Неформально выводимость на уровне ^ обозначает применение продукции к вспомогательному символу, являющемуся индексом % - того уровня. Слово Ч выводится из

9 I" слова ее на уровне я (обозначается ос|—если существует последовательность слов такая; что либо I ^ * для ^ € Р и 1г »либо ^^ получается из заменой обозначения на 1(ЯВ) на максимальном уровне, т.е. В не имеет индекса.

Язык Ц(? = —- зс],образованный из слов, выводимых на уровне к , назовем индексным языком уровня к ; а язык Ца~)={хеЕ*|ЗК201-^ *)} - индексным языком уровняло. Через будем обозначать класс индексных языков уровня & , а также класс индексных грамматик уровня ^ , если это не приводит к двусмысленности.

Пару будем называть индексной грамматикой уровня 4 . Ясно, что I-и I—-совпадают, а выводимость!—совпадает с выводимостью н бесконтекстной грамматике.

По грамматике (С[Д) легко построить грамматику порождающую тот же язык, что и (С^-к) , такую, что в выводах грамматики С}' продукции (вида ) на уровне 4 не применяются.

После преобразования применение продукции Я ВС на уровне к моделируется интерпретационным правилом 1'(Н ) = ( Н, Я) , где (Н,А) новый вспомогательный символ, и применением продукций: (Н,Я) и

Н,В) —* Н В . Кроме того вводится продукция: н ,я)—- 1(нй).

При Ь.

В ряде случаев элементы множества У(<») будем называть словами. При этом элементы множества будем называть одноэтажными словами, а элементы множества ^ ^ - этажными словами.

Замечание I. Недетерминированной интерпретацией называется отображение 11V —* [конечные подмножества языка уиупл.

Можно расширить определение индексной грамматики, допустив нетерминированные интерпретации* Тогда при применении интерпретационного правила изображение Л* будет заменяться на произвольное слово из . Как следует из[9], для каадой индексной грамматики (любого уровня) о недетерминированной интерпретацией можно построить эквивалентную индексную грамматику с детерминированной интерпретацией. К множеству вспомогательных символов старой грамматики добавляются пары (Я ,13) вспомогательных символов старой грамматики и добавляется правило = (Я,^).

К продукциям старой грамматики добавляются продукции (Д,В)-*со. если Со е I (А В) • Аналогично доказывается, что доопределение тупиковых изображений; включающих основные символы с помощью равенства $ = б' и соглашение о применении продукций вида Я -*• I только к тем вспомогательным символам} у которых нет индексов, не изменяют порождающей способности индексных грамматик*

Левыми вспомогательными символами в слове х . где эс€£ и Й€У 9 назовем Я и все левые вспомогательные символы из ^ . Таким образом в - этажном слове может быть & левых вспомогательных символов. Назовем вывод в индексной грамматике левым; если правила вывода применяются торко к левым вспомогательным символам.

Ясно, что из каждого вывода перестановкой применения правил можно получмь левый вывод; приводящий к тому же результату.

§ 2. Основные свойства классов .

Теорема I. Класс языков совпадает с классом рекурсивно-перечислимых языков.

Доказательство. Пусть Т - преобразователь с конечным числом состояний $>- £ , который, находясь в состоянии $. 7 читает на входной ленте символ б'е 2 в зависимости от и 6* переходит в новое состояние и в это же время на выходной ленте печатает слово

Пусть Т(£г-,х)- слово, напечатанное на выходной ленте» если преобразователь Т ; начав из состояния , прочитал на выходной ленте слово X •

Легко построить индексную грамматику С (Т) , среди вспомогательных символов которой имеются символы € £ , гН такую,что £>. »-Т(5г.;зс)Н . Вспомогательными символами грамматики являются: Н ) е £; И;($¿,60,где ^€ Е; и тупиковый символ Ф . Имеются проду кцииг^^О^СУ$ и * Н , Интерпретация задается равенствами: во всех остальных случаях« Далее для простоты будем полагать, что алфавит 2 содержит только два символа 0 и 1« м ^

Пусть (х,тг) осе{0,1^ конфигурация в момент ^ одноленточной машины Тьюринга М , которая вычисляет всюду определенную функцию (ОД] —► , множество значений которой есть заданное реяурсивно-перечислимое множество, л уу если начальная конфигурация равняется х л у где ср0 -начальное состояние машины М , а ^ - изображение пуотой ячейки» Можно считать, что головка машины М не заходит левее ячейки, обозреваемой в начальный момент. Пусть 1д(х) -число пустых в начальный момент ячеек, которые используются машиной М при работе над словом X. Тогда существует преоб-разователь Тм , отображающий Я (ос, Цх)) в И (х,Цос))3 если начальное состояние преобразователяТм равняется Я •

Грамматику из 8 , порождающую заданное рекурсивно--перечислимое множество 2 , можно получить из (} (Тм)7 добавив: а) вспомогательные символы В; С', 0;

- состояния машины М , Л - изображение пустой ячейки; б) продукции: Я-Р* Я-ВН; В-ВЭ^ В^С; ОСГ^С-Со с^у— е ? где заключительное состояние машины М , и объявив нетерминал Я начальным* Ясно, что построенная грамматика порождает только конфигурации машины И , и следовательно, ее терминальные порождения являются элементами из2. Пусть М вычисляет начиная с на рабочей зоне П/ за время Ь « Применим продукцию Й-*Я ровно "Ь раз на самом верхнем уровне, а затем й—ЪН и "В1—* После этого любое, не заходящее в тупик, продолжение вывода приводит к слову х* Теорема доказана*

Далее будут рассмотрены классы , к < 00 .В лемме I доказывается возможность приведения грамматик из к специальной форме, а в теореме 2, используя это приведение, доказывается разрешимость проблемы пустоты порождаемого языка для классов грамматик .

Из теоремы 2 и из конструктивной замкнутости классов относительно пересечения с регулярными языками (лемма 2) следует разрешимость проблемы принадлежности*

В теореме 3 усиливается результат леммы I (осуществляется приведение к приведенной форме; в отличии от формы, указанной в лемме I, здеоь запрещено порождение пустого слова, кроме как в начальный момент). Приведенная форма используется в § 4 для доказательства эквивалентности класса грамматик и класса автоматов УЯ^ .

В теореме 4 показана возможность перехода от класса регулярных языков к классу бесконтекстных языков тем же способом, которым осуществляется переход от Э^к ♦

Лемма 1« Для данной индексной грамматики уровня Ь. можно построить порождающую тот же язык индексную грамматику уровня {г , имеющую продукции вида ? Й^ВС^ А С или А I .

Доказательство« Последовательно производим замены продукций:

1) продукцию А-ь&> » где со= еу со^Ф & и либо <о£4 V , либо V $ заменяем на три продукции А -»-ВС &-*соА и С^соагде В и С - новые вспомогательные символы;

2) продукцию Я -+ЪЫ , где 0)^еи со^У заменяем на две продукции Ссо , где С - новый вспомогательный символ.

При проведении замен (I) и (2) уменьшается максимальное число букв, входящих в правые части продукций, до двух букв.

Теперь остается только избавится от продукций вида И-»В . Это достигается введением нового вспомогательного символа 2 , продукции и заменой каздой продукции на Для расширения интерпретации введем тупиковый символ ф и положим I (А для тех пар А и В, для которых 1(ЯВ) еще не определено.

Лемма 2. Для каждого & класс языков Э^ конструктивно замкнут относительно пересечения с регулярными языками.

Доказательство. Пусть задана индексная грамматика уровня Ь .С-,1,Я0>, где порождаада$вмк.Ц . Пусть 5= [50> ^Ч,-.,~ множество состояний (30- начальное) данного конечного автомата» представляющего языкИ , а | - функция переходов этого автомата.

Вспомогательными символами новой индексной грамматики уровня Сбудут тройки 1А 7 ^ ? и [^г , » *0пользуемые только на первом этаже, старые вспомогательные символы и начальный символ В0 . Будем считать, что продукции грамматики § имеют вид указанный в лемме I. Новая грамматика содержит продукции:

I) [30? До , где заключительное состояние;

3) КЯ^Ь&ЛАЛ, волИ(йГй;>? ^ ,в", , вели (Яре)еР;

6> [^.Р^^^воа

7) все продукции грамматики , Интерпретация новой граи матшш задается с помощью равенств, входящих в определение интерпретации грамматики ^ и равенств = если I (Я* Ясно; что новая грамматика порождает язык I* П .

Теорема 2. Для индексных грамматик уровня Ь, {коо ? разрешима проблема пустоты порождаемого языка.

Доказательство. Для индексных грамматик уровня I (бесконтекстных) разрешимость проблемы пустоты известна [21]. Пусть разрешимость проблемы пустоты доказана для индексных грамматик уровней I» 2, «••> • Сведем проблемуцустоты для заданной индексной грамматики £ уровня & к проблеме пустоты для индексной грамматики С?'уровня • Предположим, что продукции грамматики I, ^о^ уровня Ь приведены к виду, указанному в лемме I. Расширим нетерминальный алфавит V , добавив символы Я - двойники символов Яе V- и тупиковый символ Ф , и будем считать £>0 новым начальным символом. Добавим к Р продукции:

X) Я - ВС , если (Я ВС)е Р ^

2) если (Я-ВС)€Р^

3) Я6 , если (А-в)€Р-,

4) Я-£ , если (Я-*£)€ Р.

Интерпретацию I расширим до 1± с помощью равенств:

1) 1(кв)'

2) (X ) = Ф в тех случаях, когда еще не определена.

Полученная грамматика А= { 2, ^, , 1£9 ) уровня к порождает тот же язык, что и грамматика и ее продукции также имеют вид, указанный в лемме I. Кроме того в выводимых словах грамматики на первом этаже стоят только символы ИСЛбУ) или Я) , или 2 , а на остальных этажах только символы Я е V .

Устраним все основные символы из правых частей продукций грамматики Полученная грамматика Сг^^, у $0) порождает пустой язык ф , если ^ порождает ф? и порождает {£} в противном случае.

Введем новые вспомогательные символы 7 Я 9 Х^] , где V , а ^ и подмножества алфавита V (т.е. элементы из )♦ Символы Л из \/А отождествим о одноэлементными подмножествами. Пусть <эс> обозначает множество символов, входящих в (одноэтажное) словосс. В грамматике С' будет иметь место выводимость в тогда и только тогда, когда в грамматике выполнено:

ЗосЗг|,(хйЛ—с

Начальным символом грамматики по-прежнему является ¿0. Грамматика ^ содержит продукции:

1) все продукции из Р2 ;

2) все продукции А [В,С!? Ф] , если (IV ВС)еР2. Я,В и С из V ;

3) все продукцииКиВ,/)7

4) все продукции [В7 А, [С9 Н, ХН^ДХ], если

5) все продукции IX, Я, ^^[Х^йД], если где обозначает выводимость в бесконтекстной грамматике, содержащей продукции вида А-* В С и й-* из ;

6) все продукции Я,а ; если «^-{Ь^,./^},

7) при ¿>2 вое продукции вел» (Я-ВС)€р, У, 6

8) при вое продукции Я, -» } воли

Л-Вс)€р.

К добавим интерпретационные правила:

1) 1(я в)=С',

2) ^(Й^Фдля тех пар й и & , для которых Iеще не определено•

Проверка равенства языков, порождаемых грамматиками(С}2, Ь) и (1-1), не представляет труда. Теорема доказана.

Из конструктивной замкнутости класса языков относительно пересечения с регулярными множествами и разрешимости проблемы пустоты вытекает разрешимость проблемы принадлежности» Следствие I» Для класса индексных языков уровня разрешима проблема принадлежности.

- • к.

Будем говорить, что грамматика в приведенной форме, если с ее продукции имеют вид Я В 5 Я — В С ^ Я 6" и, возможно, £ , где начальный символ, причем о. не входит ¿^равые части продукций и интерпретационных правил»

Теорема 3. По индексной грамматике можно построит] эквивалентную индексную грамматику ((}',в приведенной форме.

Доказательство. Не уменьшая общности можно считать, что приведена к виду, указанному в лемме I, т.е. ее продукции имеют вид Й А—'ВС, Я -»в или

Преобразование грамматики § к состоит из следующих этапов:

1) Произведем разделение алфавита вспомогательных символов (см. § 4). После этого множества символов, которые могут появляться на г -том этаже, станут непересекающимися. Полученный алфавит вспомогательных символов будем обозначать через V (V- иУ(г)).

1»

2) На всех этажах выше первого заменим применения продукций Я на Я-»Б , где Е новый вспомогательный символ, обладающий свойством: КвЕ) =В для каждого вспомогательного символа В .

3) Вспомогательному символу Я на первом этаже может быть придано в качестве параметра (обозначается ) некоторое подмножество $ вспомогательных символов первого этажа, каждый из которых под влиянием находящихся над ним индексов имеет возможность перейти в пустое слово (в противном случае вывод заходит в тупик).

4) Если при некотором применении продукции /1 ВС на первом этаже в выводе грамматики С| предлагается, что В или С! в дальнейшем перейдет под влиянием находящихся над ним индексов в пустое слово, то добавим это В или С? к параметру другого, т.е. применим продукцию или [Я Л/]—* [В7Си чМ ] . Введем также продукции [я*]-я и я-[я,*], где Я?В и С ивУ(0, а Хе 2У.

5) Добавим вспомогательные символы второго этажа: в, В , где подмножества из V(1), а В символ из У(2)иЕ. Добавим продукции

С?" если в § имелась продукция А—В # позволяющие на период времени от порождения индекса С до исчезновения всех его наследников избавиться от параметров*

6) Введем продукции В-»ВВ и В где В символ из У(2)иЕ; а ^ подмножества символов из 4(1). Введем интерпретационные правила позволяющие кроме прочего ликвидировать последствия продукций из 5). В подслове[Я,У1]В применение введенных продукций и интерпретационных правил обозначает, что В , используя , переводит в ,т,е 3 о. Зу (<*>= = ее*" у).

7) Правила (продукции и интерпретационные) для обращения со вспомогательными символами совпадают с введенными в теореме 2, но только продукции X —> £ заменяются на Х—Е, а знак Я заменяется на = . Вспомогательный символ В из \/(2)иЕ преобразуется, используя те же правила, которые были применимы к В до пункта 6, но черта сохраняется над всеми его наследниками. Интерпретационные правила для ь имеют вид

8) Добавим продукции [Я,^]-* [Я,Х1 ? еслй

3 х (<х>- № > - * X у) .

9) Теперь необходимо избавиться от продукций вида Й->В . Для этого заменим каждый вспомогательный символ А на [А]= в й 1 ^ ■ В}. Нетерминалами новой грамматики будут подмножества нетерминалов старой грамматики; [£>0] начальный. Продукции соответствуют продукциям старой грамматики:

1) М [В, С! ] , если А € У и была продукция Я — В С ;

2) [В] ^ , если ЯбХ и была продукция ;

3) 6" , если Я еУ и была продукция Я ^ Интерпретационные правила задаются равенствами:

К^ЛИХ |ЭЯ,Ъ ДЯе^БеУ^ I(А в)= С 4С ^ X)}.

10) Полученная грамматика эквивалентна грамматике с точностью до пустого слова. В случае необходимости можно добавить продукцию [5(3 —» £ . Теорема доказана.

В теореме 4 предполагаем, что тупики доопределены равенствами 5 « Б .

Теорема Подкласс индексных грамматик уровня 2 с продукциями вида Л—Я —«* в 9 й —- и порождает класс бесконтекстных языков.

Доказательство. Для каждой бесконтекстной грамматики (¡! существует эквивалентная бесконтекстная грамматика = в приведенной форме[21], т.е. с продукциями вида \ А * В (! или Я-* Ь . Для нее можно построить индексную грамматику с алфавитом вспомогательных символов У[)ЧМгф) » где V - { Я | Я С VI, и с продукциями

1) А-&С, если (А — ЕС) € Р ;

2) А- £ , если (А-г) ер ;

3) (Я,В)-+6В , если (А^б)бР и ВеУ;

4) А — ? если (Я -*е)€Р;

5)(И,В)-^В, если (Я е) е Р , и интерпретационными правилами:

1) 1(Я В) = (Я,В) для всех Я и В из V ;

2) I (Х^Ф в остальных случаях. Начальный нетерминал

Ясно, что !*(<;,)и совпадают.

Далее, по индексной грамматике (} = (И ,\/,Р Д ,$0) указанного в теореме вида можно построить допускающий магазинный автомат с множеством состояний К=Уи{$} , магазинным алфавитом Г=\/и{£}; начальным состоянием , допускающим состоянием 5 , начальным магазинным символом ¿0 и функцией действия:

1. <ХХ) всли (Я-бВ)еР и ХеГ;

2. 8(Я,в,Х) = (Х,е) , если (Я-^е)еР и ХеУ;

3. 8(Я,Й,Х) = (В,СХ) , если (Я- Вс)€р И ХеГ; 8(^)0-($,£) , если (А — £)€Р и ХеГ;

5. 8(Я,6,В)=(С>£) , если 1(АВ)=С 8(Я,Мо)в (МЛ .^о» (Я^в)бР .

Ясно, что автомат допускает язык, порождаемый грамматикой который поэтому бесконтекстен. Теорема доказана*

Теорема показывает, что переход от конечноавтоматных языков к бесконтекстным можно осуществить тем же способом, что и переход от класса к для .

§ 3. Связь с грамматиками Вейнгаардена

Теперь мы покажем, что некоторый подкласс (с однозначными понятиями) грамматик Вейнгаардена, использованных для описания Алгола 68 ^23 и 24|; порождает класс языков, содержащихся в третьем члене вышеприведенной последовательности классов индексных языков.

Грамматикой Вейнгаардена (или V - грамматикой) называется шестерка \Х/= (2,Г?Р7#,07 Х0)?где -конечный алфавит основных символов^Г= (II7М-{М1}. - бесконтекстная грамматика (без начального символа), ее вспомогательные символы М; называются метапонятиями, С

V ^ конечный набор нродукций (метаправил) грамматики Г; # и ф -символы, не входящие в£ , Р - конечное множество пар Х~>У, X € (ЕII М)+,Уб (И и И и # О])* называемых гиперправи-лами, слово X называется порождающим, слово V - списком с разделителем О , Хс€ 2 - начальное слово*

Слова(из2* ), выводимые в грамматике М? С7 М^} называются порождениями метапонятия М^ в грамматике Т* •

Понятиями называются результаты подстановок в порождающие слова X вместо всех метапонятий М

В [23] и [24] вместо маркера#используется * вутЪо1*, , вместо разделителя О используется и вместо Х0 используется »рговгат» • Кроме того предполагается, что к порождаемому языку применяется некоторый гомоморфизм к(<>)= ¿^переводящий его в язык представления.

На первом этапе вывода в грамматике V/ у нас имеется слово Х0 . На каждом следующем (промежуточное) слово Н из Д=((2*и2 #)<>) (2 и2*#).Слово 2 разбивается раз-делителемОна слова , некоторые из которых являются понятиями и называются вспомогательными, некоторые заканчиваются на # и называются основными, а остальные являются тупиками* Переход к следующему этапу осуществляется заменой некоторого ^ , являющегося понятием в на сое Д при наличии порождающего правила (З^^-со . э^ап вывода Н = р1<>,.<>со<>.оО/И/ из Ъ обозначается или , а транзитивное замыкание через .

Грамматикой V порождается язык

Пример^- грамматики.

Пусть задана порождающая грамматика (} - , ? У , Грамматика Вейнгаардена <Ц <Е \)V, {X

У-* , 2 -* £ 7 со и У-» а/ для каждого ае 2 и 2 а, для каждого аеЕ}>, {н-*- 2#0 иХ

При рассмотрении деревьев выводов в приведенном примере можно заметить, что одно и тоже понятие получается с помощью нескольких различных подстановок порождений метапоня-тий в порождающие слова. Ниже будет показано, что именно эта возможность является причиной неразрешимости проблем пустоты и принадлежности для грамматик Вейнгаардена.

Неформально грамматика Вейнгаардена является бесконтекстной грамматикой с бесконечными алфавитами основных я вспомогательных символов и с бесконечным числом продукций. Но это бесконечное множество продукций имеет простую структуру, Продукции (порождающие правила) получаются из конечного множества гиперправил подстановкой слов из заданных бесконтекстных языков вместо некоторых символов в гиперправилах (вместо всех вхождений заменяемого символа подставляется одно и тоже слово). Бесконечное множество основных символов - это множество слов (в конечном алфавите), заканчивающихся на специальный маркер. Фактически порождаемый грамматикой Вейнгаардена язык также определен в этом конечном алфавите, если основные символы понимать как их записи.

Пусть - поровдающее правило] и (у. 13"У СУ -'У4о. оУ; о .0У^(У€(£ и м)*)ФЗХ (Х-У порождающее правило))} и 0 ¿= [У. 13У((.ОУ<>.

У^ £ (2 и М) 3 X (X —* У — порождающее правил^

Определение 2.[14] Грамматику ВейнгаарденаV будем называть грамматикой с однозначными понятиями (или 1Х\х/ V грамматикой), если:

1) для каждого понятия Я=Х(©^)существует единственное слово Х€ и единственная подстановка ы порождений метапонятий, входящих в X , с помощью которой из X можно получить Я =Х(Ц) ;

2) для каждого основного слова 2 = Х(о<),где о^ - порождения метапонятий из X , существует единственное слово и единственная подстановка порождений метапонятий; входящих в X , с помощью которой из X можно получить 2 = Х(*>

Замечание 2. ДляШх/- грамматик не уменьшая общности можно считать, что разбиение промежуточного слова И разделителями О на любом этапе любого вывода 1ДйС грамматики не содержит тупиков (либо Х^- тупик), т.к. если гиперправилу соответствует хотя бы одно порождающее правило с тупиком в правой части, то все соответствующие ему порождающие правила содержат тупики в правых частях, следовательно,это гиперправило можно ликвидировать.

Замечание 3. Не уменьшая общности можно считать, что все продукции мет arpa мма тики имеют вид Я-Я —* Вб* или Я —»■ В С Б' (приведение к такой форме см.[7]).

Замечание Назовем левым выводом в W - грамматике такой вывод, в котором порождающие правила применяются к самым левым вхождениям понятий в промежуточные слова вывода. Для каждого слова х , выводимого в данной W- грамма-тике, существует левый вывод, полученный из любого вывода слова х изменением порядка применения порождающих правил«

Примеры UW - грамматик:

1. Пусть задана бесконтекстная грамматика T1=(2)V)PJX)5 порождающаяязык. и.

ILW- грамматика порождает язык

2. Следующий пример близок к фрагментам языков программирования.

Алфавит основных символов 5Z = [(Дj, , > 5, метаграмматика Т-= [I ,Я,В^ С ] 9 где С содержит метаправила: I-*^ I, I-* ,1— Я^^В^Я^.Множество Р содержит гиперправила:

Л $0 #0;#0 Б30;#0 Я #0+#0В#0)# и г .

Начальным словом является В • 3

Если терминальные порождения метапонятия I понимать как описания, то операция + в порождаемых грамматикой цепочках применяется только к операндам с одинаковыми описателями, т.е. перед должны встретиться поихп и 1 на том же уровне скобочной вложенности.

Известно, что проблема принадлежности данного слова языку, порождаемому данной грамматикой Вейнгаардена?неразре-шима [13]. Г.С.Цейтин выдвинул предположение, что можно выделить достаточно широкий подкласс грамматик Вейнгаарде-на, для которого проблема принадлежности разрешима. Мы покажем, что таким подклассом является класс грамматик Вейн-гаардена с однозначными понятиями.

Теорема 5. По каждой грамматике Вейнгаардена с однозначными понятиями и\х/ можно построить индексную грамматику уровня 3 (у ^ » порождающую тот же язык, что и порождаемый грамматикой

Доказательство. Прежде всего отметим следующее свойство Шх/- грамматик. Пусть 2. - промежуточное слово в некотором выводе слова ос в заданной 16У - грамматике. И пусть И — . ( где не содержат О . Тогда для каждого (в силу однозначности и замечания 2) существует единственное в и 0а и единственная подстановка терминальных порождений метапонятий, входящих в , такие, что результат этой подстановки есть . Таким образом определены отображение Е —► Е 9 где 2= О^О.^.Об^, и выводимость ? где ^ осуществляется применением гиперправила, соответствующего порождающему правилу, применяемому на шаге вывода Е^ => 0 т.е.

2.-0,0.^, г.,о.но.о

- 14 не содержит 07 О 3?г ? и имеется гиперправило V ■ в грамматике Ю\Х/Г.

Таким образом имеется коммутативная диаграмма и)

Если на шаге вывода об«, и 2.-01о.оО.1оУоб.+1о.о б^, применялось гиперправило

Х-У Х=Х1МХг И У=ХМУ2 то вхождения М в Zi , стоящее сразу же справу от ив 2гЧ1 стоящее сразу же справа от О <>? считаем непосредственно связанными. А также считаем непосредственно связанными все вхождения М в между которыми нет разделителя . Транзитивное и симметричное замыкание отношения непосредственной связанности назовем отношением связанности. Итак, каждое слово X из и только слова из можно вывести из применением гиперправил с последующей подстановкой вместо метапонятий их терминальных порождений, проследив однако за равенствами подстановок вместо связанных метапонятий.

Ниже построенная грамматика , моделирующая заданную КV- грамматику, будет осуществлять такой разделенный способ вывода.

Пусть задана ЦУ- грамматика и Г-<2,М-[М„.,Ме),С>, £ = рС-У]. Каждое У см. замечание 2) делится разделителем О на подслова б; } каждое - порождающее или основное слово.

Алфавит основных символов моделирующей грамматики — это 2 и О } • Алфавит вспомогательных символов грамматики содержит следующие группы символов:

1) - двойники к алфавиту 2 .

2) Все метапонятия М грамматикиМАх/и двойники мета-понятий М ;

3) все упорядоченные по возрастанию индекса подмножества метапонятий £ Мг* Мг- } , пустое под-множество метапонятий отоядествляется с пустым словом £ ;

4) символИ , указывающий окончание некоторого этапа вывода;

5) все пары вида (М^М-) или (М^/К) , где

М.И м. А метапонятия;

6) все символы = " , где М - метапонятие;

7) все X"такие, что

8) все , не содержащие О такие, что те из них, которые не оканчиваются маркером » совпадают с соответствующими элементами из пункта 7;

9) все V такие, что 10) символ 2 , указывающий на незавершенность некоторого этапа вывода;

II) тупиковый символ Ф . Символ является начальным. о

Грамматика имеет следующие продукции:

1) все продукции вида Х"^^' ? где (Х-^ОбР и X состоит из тех метапонятий, которые входят в"У, но не входят в X ;

2) все продукции вида чЯ-* (М^ 1 у где

-[М^и^ и Л;

3) вое продукции вида (М^ МЛ(М^)*^" ? где

Мре)еС- 1 все продукции вида (М^ ? Мг) (М^М^У'б" у где все продукции вида (М,-, М;)-*(М- Мь) 6'\гдв (М:- V * '

4) всё продукции Ч —► У> где

Интерпретация I грамматики задается равенствами 1-8, где и М? - метапонятия, а Л/ - непустое подмножество о метапонятий.

1) КСМ^О-СМ^МЛ;

2) ; 3) 1((М,Ъ)5)= 3«М=И ;

1("М="3>вМ=", 1("вя11>гб".

5) К^'*)--«.^. , где У-в10.<>а№правая часть некоторого гиперправила, а не содержат О- ;

6) 1(м;м'-")-М{, 1(Г6>бЙ, 1(М3)=6Д(МР"> -М. ПРИ 1(М"е")=М, 1(М3)= М'

7) для всех остальных пар нетерминалов

Я и В:1(йвМ>.

Предполагаем, что для символов $€Еи(#,<>Звыполнено 6 =

В продукциях 4 указан способ получения слова б из вспоил" -г могательного символа Ы • Равенства 1-4 используются вместе с продукциями для построения поровдения метапонятияМ, располагаемого правее символа Г'М=" • Равенство 5 позволяет расщепить СУ* , когда построены порождения для всех входящих в У метапонятий. Равенства 6 осуществляют подстановку порождений метапонятий.

Равенство языков, порожденных грамматиками!^,^) и Ш/ вытекает из утверждений а) - г) . а) Пусть Т^ - множество одноэтажных слов, выводимых из вспомогательного символа

И Й* е Т^ ) . тогда Н,- • • порождения метапонятий М^. о ^

Далее (до конца параграфа) введем следующие изменения

1— в обозначениях. Чер£ЗкЧ5удем обозначать одношаговый вывод (т.е. применение продукции на первом или втором уровне или применение интерпретационного правила) в грамматике (Съ?Ъ) , а через ^ транзитивное замыкание дл*я^(раньше V-*- обозначалось I—± ). Пусть Х^УеР и У^О^.ОО где& не содержат О , тогда Р^Х^^У'***"?*^^* . У | Н - множество подвыводов в (}5 , у» «\Г> ^^ начинающихся применением правила А —* т и заканчивающихся первым вхождением интерпретации и все нетупиковые выводы со в А имеют начало в F (х)= и б) Рассмотрим вывод Х = Ъ. в-^рамматикеКЛ)/. Пусть и Иг»+1 определяется по iv1

Ту и 2-Об^О.-Об^ равенством: гЧ1= ц± 1 о.о О ТО ч^ ' о.-о Ч*. , при * У(|Чу) " порождающее правило, примененное на шаге вывода £г-п,(Х-*У)€Р , ~ порождения метапонятий М^.^М^ входящих в У , но не входящих в ™Р10»„ ОРг 9 где не содержат О и ^«{М^,., М-Д, получено из Г что НгЧ1 , идля каждого f<>,. если соответствующие и (определяемые диаграммой О) ) имеют связанные вхождения метапонятия М , т<

Ц={чМ=\ал, кх къ не содержат символ С'М-", ^ и не содержат символ 5 и . Если же эти вхождения метапонятия М не связаны, то ^ и могут быть любыми порождениями метапонятия М , в) Если 0*0/' и -основное слово* то выводится из '•в грамматике см, продукции 4 и равенства 6 определения интерпретации). Таким образом I* (ИЛУ) Я Iк ((} ь , Ъ) . г) Заметим, что каждый левый ныводОС^Е^— Е^- ос в грамматике С[3 разбивается применениями продукций (из группы 1) к символу на первом этаже на подвыводы Е =ЕЕ'^

I \\

Е^.,*^ ? где подвыводыЕ^Е^ к л начинаются применением продукции из группы I, а завершаются применением интерпретационного правила из группы 5, а подвыводы получены последовательностью (возможно, пустой) продукций из группы 4 и интерпретационных правил, заданных равенствами 6» Построим левый вывод Х0= И=е> ос в грамматике 1С\Х/ , в котором на шаге применяется порождающее правило если подвывод Е^.Ь^-Е^. начинался продукцией Л. )— У , а значения о/у р и ^ определяются ниже* Пусть ^ - цепочка индексов символа "X" , к которому применяется продукция. Пус^ь^Х'^^'^^^Тч получено из в подвыводе Е^н-*— тогда * Значения подстановок и р определяются по цепочке С : если 1ъ= ^ ^ не содержит символ аМ=и , а ^ не содержит символ $ , то вместо М подставляется его терминальное порождение ^ * Ясно, что 2.-Е,;. . Итак, Ъ)Я1*(%\

Заметим, что последнее включение не зависит от того, является ли грамматика И\х/ грамматикой с однозначными понятиями.

Следствие 2. Из следствия I и теоремы 5 вытекает разрешимость проблемы принадлежности слова к языку, порождаемому грамматикой Вейнгаардена с однозначными понятиями.

Таким образом, индексные грамматики уровня ©о • как и грамматики Вейнгаардена[13]порождают класс рекурсивно-перечеслимых языков. Грамматики Вейнгаярцена с однозначными понятиями порождают класс языков V » вложенный в класс индексных языков уровня 3. В [Зб] построен пример не индексного языка вида VI \\/£ , где 1, некоторый бесконтекстный язык. Для этого языка легко построить пороэдаю-щую его НУ -грамматику. Поэтому класс не содержится в классе .

§ 4. Многоуровневые магазинные автоматы

Йагазинной памятью уровня I является обычный магазин (из символов), а магазинной памятью уровня I является магазинный список (который будем считать расположенным верти кально) памятей уровня С -I» Действия с магазинной памятью уровня I описаны в [21, 22] . Над магазинной памятью уровня I можно совершить следующие действия (точное определение будет дано ниже):

1) все допустимые действия над её верхней памятью уровня с -I;

2) заменить верхнюю память уровня I -1 на две с ней совпадающие;

3) заменить активный символ.

При опустошении вершинной памяти уровня I -I автомат переходит к следующей памяти уровня I -I.

Память уровня I удобно рассматривать расположенной в I -мерном пространстве так, чтобы элементы магазинного списка (памяти уровня I -I) занимали параллельные гиперплоскости; при действии 2 происходит дублирование верхней гиперплоскости,

В промежуточных словах выводов индексных грамматик уровня один и тот же вспомогательный символ может встречаться на разных этапах. При можно» однако, по данной индексной грамматике уровня & построить эквивалентную ей такую, чтобы каждый вспомогательный символ мог встречаться на каком-то одном (своем) этаже. Для этого каждый вспомогательный символ Я заменим на & вспомогательных символов » а каадю продукцию А-*-со на Ц продукций Л (г) -> со (0, к; где Со (г) получено из со заменой кавдого вхождения вспомогательного символа В на | - том этаже слова и на ; если для некоторого г и некоторого вхождения В в со выполнено i+j-L>kf то продукция Я (г) со(г) ликвидируется. Каждое интерпретационное правило 1(Я&)=С заменим на правило После указанного преобразования нетерминальный алфавит будем называть разделенным .

Класс бесконтекстных языков совпадает с классом языков допускаемых нетерминированными магазинными автоматами [21,25] Аналогичную роль для индексных языков уровня 4+2 играют магазинные автоматы уровня

Действия магазинного автомата (с одним состоянием) совпадают с левым выводом в бесконтекстной грамматике, продукции которой приведены к виду: А—ВС или А-*6\ В этом случае при левом выводе часть промежуточного слова, состоящую из вспомогательных символов, можно рассматривать как содержимое магазина.

Продукции индексной грамматики можно привести (как доказано в теореме 3) к виду А-*ВС» А-*В или А-*6", Будем считать, что нетерминальный алфавит разделен по этажам. Промежуточное слово при левом выводе имеет вид 6; . 6; Я,-1,. Л,* н;€У(оо). Часть из вспомогэтельных символов должна естественным образом располагаться в памяти допускающего автомата.

Память уровня I - это магазин символов. Автомат может совершать с магазином следующие действия: прочитать очередной символ на входной ленте и верхний символ магазина, а затем стереть последний; 2) прочитать и заменить на два символа верхний символ в магазине.

Память уровня 2 - это магазин пар: активный символ -магазин символов . Автомат работает с верхней парой магазина. При опустошении верхней пары автомат переходит к следующей (становящейся верхней) паре. Автомат может совершать следующие действия над верхней парой, возможность выполнения которых зависит от читаемых символов: 1) если магазин в верхней паре пуст, то прочитать очередной символ на входной ленте и активный символ, а затем стереть верхнюю пару; 2) прочитать активный символ и заменить верхнюю пару на две отличающихся от первоначальной лишь активным символом; 3) прочитать активный символ и заменить его, добавив при этом символ в вершину магазина символов;

4) прочитать активный символ и верхний символ магазина, затем стереть верхний символ магазина и изменить активный символ, В левом выводе активные символы соответствуют первому этапу, а остальные символы памяти второму этажу (см, рис, I),

Память уровня к - это магазин пар: активный символ -память уровня 1 . Автомат работает с верхней парой, а при ее опустошений переходит к следующей паре. Пусть верхней парой в памяти уровня к является (>>, М^) • Автомат может совершать (недетерминированно) следующие действия, возможность выполнения которых зависит от читаемых символов (символ на входной ленте не читается, если не указано обратное):

I) если память М^ уровня Ц- I в верхней паре пуста, то прочитать очередной символ на входной ленте и активный символ $ верхней пары, а затем стереть верхнюю пару;

2) прочитать активный символ 2 верхней пары и заменить верхнюю пару на две, отличающихся от первоначальной лишь активным символом;

3) прочитать активный символ ь> верхней пары и изменить его, добавив при этом верхний символ в память М^ уровня Ь-1 (т.е. в вершину магазина уровня &-1 добавить пару4:некоторый символ - пустая память уровня ¿-2» );

4) прочитать активный символ верхней пары и активный символ из верхней пары из М ^ , если при этом память уровня Ь -2 (верхняя в памяти М ) пуста, то стереть верхнюю пару в памяти и изменить прочитанный актив

- ный символ;

5) совершить одно из действий 2-5 с памятью М^ (уровня Ь,-I, находящейся в верхней паре),

В начальный момент в магазине хранится единственная пара <£начальный символ - пустая память уровня Если прочитав слово автомат опустошил память, слово считается допустимым. Ясно, что левый вывод в грамматике уровня¡1+Х и допустимость соответствующим автоматом (с одним состоянием), использующим память уровня тождественны. Отметим, что гнездный стэк [8]получается из автомата с памятью уровня 2 отождествлением совпадающих начал у составляющих магазинов.

Теперь мы покажем, что конечноавтоматное управление (ре-вым) выводом в индексных грамматиках любого уровня не расширяет класс выводимых языков. И это позволит определить классы автоматов, допускающих индексные языки заданного уровня.

Пусть продукциям и интерпретационным правилам индексной грамматики с разделенным вспомогательным алфавитом приписаны номера и имеется конечный недетерминированный автомат 1С с входным алфавитом Каждому левому выводу в индексной грамматике (2 соответствует строка г, .Л. номеров применявшихся правил (т.е. продукций или интерпре- ' тационных правил). Будем называть вывод допустимым автоматом % , если ему соответствует строка . , допустимая автоматом 16. Множество слов, полученных допустимыми выводами, обозначим через

Теорема 6. Пусть (} -индексная грамматика уровня & с разделенным вспомогательным алфавитом^ 5-множество номеров правил грамматики С[ , а ^ -конечный недетерминированный автомат с входным алфавитом . Тогда к индексный язык уровня Ь. .

Доказательство. Вспомогательному символу А на первом этаже придадим два состояния С^ и , и будем выводить из А, используя его индексы, такие слова из основного алфавита, что использованная последовательность правил (точнее, их номеров) переводит в ^ . При левом выводе информация о применении правила на любом этаже может беспрепятственно достичь первого этажа.

Формально. Пусть индексная грамматика (¡[ ^{^С^РД^) в приведенной форме и автомат У угд®

Л: Й х - начальное, а С^ заключительное состояние. Введем новые вспомогательные символы: Я, где ЯеУ, ^сб, О ; , где

3) Ф - тупиковый символ. Символ [с^Д,^] начальный.

Символ [с^. ? Я, с^.] обозначает, что из Д (вместе с его индексами) в дальнейшем будет выведено слово в основном алфавите таким образом, что строка номеров правил этого подвывода может перевести состояние С/, автомата 11 в а. . Сим

Уъ Ч вол обозначает, что на некотором этаже (но не на первом) применено правило с номером Ч. таким, что 3

Определим продукции индексной грамматики §{%) уровня , порождающей язык 1*: где ъ номер продукции Д-» £ ; г) > если Н0МеР Пр0ДУК"" ции А ВС; з) ^ЛУ-^.М;] , .«(Л^в )е1? и е -Я(о , где г. номер продукции А-»В ; * я - («мры, вой (Я-ч)бР, где г номер продукции Я —» со ;

5) , воли (Ь5>?! где ъ- номер продукций

Интерпретация грамматики С^СЦ) задается равенствами:

1) если 1(ЯВ)=Си где % номер интерпретационного правила 1(Я )= С ;

2) , если С и а 3 } г) , где % номер интерпретационного правила

3) где ЯеУ^ев^еО;

5) (X )=Ф в тех случаях, когда еще не определена.

Левые выводы грамматики (1С) моделируют левые выводы грамматики СЦ и действия автомата 16 . Теорема доказана.

Рассмотрим следующее устройство. Конечный недетерминированный автомат 16 с входным алфавитом 2 , к которому присоединена память уровня Ь. , причем автомат К/ имеет доступ к активный символам на всех уровнях* Автомат V/ читает входной символ (или S ) и активные символы (если вер-шинная память уровня ь состоит из активного символа и пустой памяти уровня 1 -I, то i нетерминальных символов и к-ъ пустых слов), затем изменяет состояние и совершает с памятью одно из действий 1-5, Заметим, что чтение активных символов можно устранить (не изменяя при этом допустимый язык), заставив автомат Vs угадывать набор активных символов и совершая соответствующие действия с памятью; если какой-то активный символ угадан неправильно, то первое же действие с ним приведет в тупик.

Итак, предположим, что у автомата устранены чтения активных символов, и что устройство допускает язык L • Заменим автомат % на недетерминированный автомат с одним состоянием, который может совершить под влиянием входного символа любое действие с присоединенной к нему памятью, которое может совершить % находясь в некотором состоянии. Последовательность действий такого автомата, приводящая к допуотимости слова ос, в точности соответствует левому выводу в некоторой индексной грамматике Q уровня к с разделенным вспомогательным алфавитом. Пусть

U недетерминированный конечный автомат, состояниями которого являются состояния автомата 16 , входной алфавит состоит из номеров правил грамматики £[, его начальное состояние - начальное состояние автомата Ъб* Под воздействием входа ^автомат U'может перейти из состояния СЬ в , если автомат М> в состоянии с^ мог совершить действие, соответствующее правилу с номером и перейти при этом в состояние . Ясно, что Сг7 К) — ^ * о ким образом доказана:

Теорема 7. Класс языков, допускаемых автоматами (недетерминированными, с конечным числом состояний) с дополнительной памятью уровня к , совпадает с классом индексных языков уровня к •

После того, как мы добавим управляющий автомат , некоторые действия над памятью могут быть представлены в виде последовательности более простых (при увеличении числа состояний автомата 16). Пусть некоторая память уровня г с активным символом Я заменяется на две памяти уровня г , пусть В активный символ верхней из этих двух памятей, а С активный символ второй (внутренней) из этих двух памятей. Тогда можно прочитать Д и запомнить номер ъ продукции А-*ВС Затем заменить активный символ Д на С. Затем изменить активный символ С на В и перейти в состояние, соответствующее номеру % и исходному состоянию. Таким образом дублирование можно производить вместо действия 2 (не изменяя при дублировании активные символы).

Далее, занумеруем все символы, которые могут записываться в память какого-либо автомата, и закодируем г -тый сим вол в этой нумерации посредством 01 0 . После этого память, использующую любое конечное число символов, можно промоделировать памятью того же уровня, использующей два символа

О и I, заменяя запись (или считывание) символа на запись или считывание) кода 01г0 .

Формально. Автомат из класса 7*1 £ это семерка М-< Г? 2 ? 5 > т Р "> , где -конечный алфавит, ¿1 конечное множество состояний, Г -конечный магазинный алфавит , ZSl Я. Г -маркеры магазинов уровней , к 7 $'(£(/{£})*&* Наконечные подмножества множества 61а (Т1*) № ]- -функция действия, £ь -начальное состояние, Г £ б- -множество заш-чительнфх состояний.

Автомат, находясь в состоянии , читая входной символ о(/ ^ по порядку от I до к 7 если (<^><¿1, »^«¿Д.) £ £$(<6 Каждому символу из I приписывается та же магазинная память уровня £ - 1 , которая была приписана ; за исключением символов XI * которым приписывается состоящая из одних маркеров память.

В начальный момент автомат находится в состоянии , обозревает самый левый символ на входной ленте и имеет магазинную память уровня , состоящую из одних маркеров.

Магазинная память уровня f, состоящая из одного маркера, - это магазин, содержащий только символ ¿1 . Магазинная память уровня Ц , состоящая из одних маркеров, - это магазин, содержащий пару: , ^ магазинная память уровня

X , состоящая из одних маркеров Я Э .

Если ©¿а =■ 8 , то стирается элемент магазинной памяти уровня I , содержащий активный символ, а нижележащий элемент становится вершинным.

Действия автомата недетерминированные С практической точ ки зрения интерес представляет подкласс детерминированных автоматов из ^^ .

Как показано выше автомат из класса ТН^ можно привести к специальному виду, когда Г= ] и

5г> либо £ < Для приведенных автоматов множество значений функции ограничено на всем классе приведенных автоматов, т.е. конечно множество сигналов, которыми обмениваются конечное ^правляющее усгройстю^автоматами ^агазинная память уровня к .

Приведенный автомат может из любой магазинной памяти уров ня перейти в магазинную память уровня ^ , состоящую из одних маркеров, если для некоторых и С^ выполнено: и о^=е в противном случае, и , если для всех г , и противном случав.

Приведенный автомат может не изменять свою магазинную память, если для некоторых , и выполнено:

V , 3>к)} >

Указанные свойства приведенных автоматов будут использованы в следующем параграфе.

§ 5. Свойства замкнутости. Системы допускающих автоматов.

В этом параграфе будет доказано, что каждое семейство языков является полным главным абстрактным семейством языков[19]. Для этого будут определены условия, при выполнении которых класс автоматов допускает семейство языков, являющееся полным главным абстрактным семейством языков. Каждый класс приведенных автоматов удовлетворяет этим условиям.

Допускающий автомат состоит из конечного недетерминированного автомата(называемого допускающей программой) и потенциально бесконечной памяти. Система допускающих автоматов определяется фиксированной памятью с конечными алфавитами символов, допускаемых каналами обмена информацией. Будем предполагать, что для памяти имеется возможность из каждого состояния ^ (за определяемое программой число шагов) перейти в начальное состояние , а также имеется возможность вернуться в . Эти условия определяют системы автоматов, допускающих полные главные абстрактные семейства языков.

Определение 3 [20]. Памятью будем называть бесконечный детерминированный частично-определенный автомат М= 8} У, } ? где X - конечный (не менее чем двубуквен-ный) алфавит входных и выходных символов, }

- бесконечное множество состояний, - начальное состояние

5*1—5► £} и частично-определенные функции переходов и выходов (т.е. чтения из памяти), соответственно.

Определение 4 [20]. Недетерминированным конечным автоматом (допускающей программой) для работы с памятью М будем называть пятерку } 7 где Тл -конечный алфавит входных символов допускающего автомата;

Р*{ро,]>*»*") р-гЛ""* конечное множество состояний, |э0 - начала ное, а ^ - заключительное состояния,р

- недетерминированная функция действия (первая координата--текущее состояние, вторая - текущий входной символ, третья

- чтение из памяти, четвертая - следующее состояние, пятая

- засылка в память). Если ^ это отображение то автомат называется детерминированным.

В каждый момент допускающая программа может считывать или не считывать очередной входной символ, но в обоих случаях она должна обмениваться информацией с памятью. Предполагаем, что память работает несколько медленнее, чем программа, поэтому программа является автоматом типа Мили (относительно засылки в память), а память - автоматом типа Мура

Взаимодействие программы в состоянии и памяти в состоянии о^ осуществляется по следующей схеме (см.рис.2). Пусть на вход автомата подан символ 2 (или б^Е ), тогда вход М равен I , выход М равен следующее состояние Я равно , следующее состояние М равно ^(с^г^ и выполнено ^(рЛЛ^ Ь ¿). Вычисление заканчивается и входное слово допускается, если Я приходит в состояние

Если память находится в состоянии и на вход памяти в этот момент подается символ ъ такой, что неопределено, или если ^Ц) неопределено, то вычисление прерывается и результат его неопределен.

Пара(|?д) называется состоянием автомата. Ясно, что конечный автомат (типа Мура) можно считать программой, у которой ^ не зависит от второго аргумента. Если 1= то память можно считать допускающим автоматом над алфавитом I , программа которого осуществляет тождественное отображение входа автомата во вход памяти и выхода памяти в выход автомата.

Аксиомы используют понятие моделирования, определением которого мы и займемся.

Определение 5. Сигнализирующей детерминированного допускающего автомата (А,М) будем называть отображение С:1 -* такое, что для всякой входной последовательности X , на которой программа не приходит в состояние (работает бесконечно долго), величина 4: ' (эс)? равная числу моментов времени | , в которые С (г-)= I (^ -сигнал, засылаемый в память в момент ^ ), неограничена.

Неформально, можно предполагать, что имеется дополнительная лента, на которой печатаются единицы при засылке в память определенных символов. Число напечатанных единиц является сигнализирующей. Незаканчивающееся вычисление имеет бесконечную сигнализирующую. Сигнализирующая прерванного вычисления неопределена*

Естественные типы сигнализирующих для машин Тьюринга время, зона для незацикливающихся вычислений, число повода,«) п л ротов) совпадают с т (ог) для некоторого I, Для С тож-дественно равного единице хс = т (ос) есть время« Данное понятие сигнализирующей фактически совпадает с понятием сигнализирующей введенным Блюмом[25].

Входным действием автомата будем называть считывание входного символа 2.

Определение 6« Детерминированный автомат (Аэ' М') моделирует с сигнализирующей С и кодом Ы (Д) детерминированный автомат (Л.М) если: , ,

2) при работе над входной последовательностью ос автомат (Р^М) в момент совершает то же входное действие, что и автомат (И, М') при работе над входной последовательностью о<(Я)х в момент \ , когда С(а,0 (г.* - засылка < л * I в память в момент ^ ) в к, -тый раз после начала считывания Ос- равняется единице; 3) в моменты, когда С(а')» автомат (й'? М') не производит входных действий.

Код существенен в тех случаях, когда необходимо моделирование нескольких автоматов*

Теперь можно сформулировать аксиомы, при выполнении ка-торых семейство автоматов допускает полное главное АСЯ.

ДО. Существует детерминированная программа Ц 0 такая, что автомат (ЙР?М) моделирует с некоторой сигнализирующей С0 память М(г0)= {1и ^^ , , где 10- новый символ, переводящий любое состояние в начальное, т.е.

Трудно назвать что-либо памятью допускающего автомата, если на ней нельзя вычислять одно и то же несколько раз подряд. Но возможно, что возврат в начальное состояние нельзя провести за один шаг*

Д1, Существует детерминированная программа Й^^ такая, что автомат моделирует с некоторой сигнализирующей СА память М(гА)= [I и {г^ 7 Л , ) ? где г^ новый символ, действующий тождественно, т.е. Для всвх й .

Все известные типы памяти автоматов без ущерба для их возможностей и сложности их описания могут быть преобразованы к виду, удовлетворяющему И. Условие А! существенно при параллельной работе нескольких устройств, а также для осуществления перекодировки входной последовательности.

Память приведенных автоматов из класса^ как показано в конце § удовлетворяет аксиомам Йои Ш.

Если полное (главное) А С Я порождается языком Ц с помощью операций, указанных в определении полного АСЯ, то это семейство обозначается 3" (Ц)» Семейство языков, допускаемое автоматами заданного семейства автоматов Ф (с общей памятью), обозначим ?№). Для языка I* в алфавите 2^,.* через (Ц) обозначим проекцию I* на г.-тую координату.

Семейство автоматов с общей памятью, удовлетворяющей аксиомам Йо и Й1 , будем называть семейством допускающих автоматов (сокращенно СФЯ ),

Ясно, что класс недетерминированных машин Тьюринга со входом с алфавитом на рабочей ленте {0,1} образуют С®Д. Следовательно рекурсивно-перечислимые языки (т.е. семейство &оо ) образуют полное главное АСЯ.

Для оо? аналогичный результат устанавливается в следующей теореме»

Теорема 8. Множество языков, допустимых семейством допускающих автоматов, образуют полное главное А С Я. Для^ данного полного главного А С Я, порождаемого языком Ь , существует семейство допускающих автоматов Ф такое, что У (Ц= ?(<£),

Доказательство. Семейство языков, допустимое данной С ФА замкнуто относительно:

1) Объединения. Достаточно взять программу, которая из начального состояния переходит (недетерминированно), не изменяя память и не читая, в одно из состояний ^ или , являющихся начальными для программ автоматов, допускающих объединяемые языки; дальше действует выбранная из этих программ. Возможность не изменить память (точнее, возможность моделировать тождественное изменение памяти) следует из аксиомы А1.

2) Пересечения с регулярными языками. Состоянию программы Я из автомата, допускающего язык Ц. , в качестве параметра придается состояние конечного недетерминированного автомата 16 с одним состоянием , допускающего язык И . Состояния программы изменяются прежним образом (независимо от параметра), а параметр изменяется только при чтении входного символа (недетерминированно, согласно функции перехода из ). Начальное (заключительное) состояние из Я с параметром, который является начальным (заключительным) состоянием из , является начальным (заключительным) состоянием программы, допускающей I* П % .

3) Гомоморфизма и обращения гомоморфизма. Новая допускающая программа состоит из конечного недетерминированного преобразователя К , осуществляющая [19]гомоморфизм или обращение гомоморфизма, и старой допускающей программы, которая рассматривает выходы К как входные символы. Получив слово на выходе К , программа А посимвольно считывает его (в это время входом К и всей новой допускающей программы является £ ), а по окончанию этого слова подает входной символ на вход К. Для гомоморфизма, который не является нестирающим, необходимо в некоторые моменты засылать в память символ ь , действующий тождественно. Возможность такой засылки (точнее, моделирования такой засылки) следует из аксиомы ¿1 •

4) Произведения и итерации. Для допустимости программа должна, допустив слово из , вернуть память в начальное состояние (возможность этого обеспечивается аксиомой Йо ) и запустить программу, допускающую . Для допустимости программа должна, обнаружив слово из К* (недетерминированно), либо вернуть память в начальное состояние и запустить программу, допускающую!*, снова, либо объявить о допустимости прочитанного слова и остановиться.

Возможность представления непустого языка вытекает из возможности для программы работать, засылая в память г0 (точнее, моделируя такую засылку) и не обращая внимания на выходы. По определению символа такое обращение с памятью не приводит к ее зацикливанию. к

Покажем, что язык I* вход-выходных пар слов памяти данной СМ является порождающим. Пусть дана допускающая программа Я* 3 , Введем обозначения что И - регулярно. Пусть ^«^(З')* (НО и . Тогда ^()аГ1(и)П11) является языком, допустимым с помощью данной программы Я •

Наоборот, пусть задано полное главное А С Я 7(1*)» порождаемое языком

Рассмотрим память М={Е и{£0Дд,-1} {,зв|х

§ч('»7г1)= х; 5(х7г0)= Л(х)= г1 при х€ И и у г0 при осеХ!; !Х(х) неопреде лена в остальных случаях» Множество вход-выходных пар памяти М принадлежат семейству 5*(I*) и порождают его, т.к. где аА. ((2 и {н)) х {})* | р (а*) = г^

Се 2 и ¿(-0 я 8 и

Теорема доказана.

Память любого конечного уровня с двумя используемыми символами удовлетворяет аксиомам АО и А1, поэтому казвдое из семейств языков образует полное главное абстрактное семейство языков. Следовательно каждый язык Ь, из 9" представим в виде 1*= ^ Я) ? где ^ и к к гомоморфизмы, И регулярный язык, а язык вход-выходных последовательностей памяти уровня Ь с алфавитом В частности, (3^ порождается грамматикой уровня 2 СККМДлг), Я,Ъ),?,!>&,}, где? содержит продукции , 30-* , $—С) а I содержит интерпретационные правила Х(50)=й/30 и 1(5®)=ц0.

Замечания : Неизвестно, для каждой ли памяти МА найдется всюду определенная память М2(т.е. функции $ и ^Х всюду определены) такая, что использующие Мх и М2семейства автоматов допускают одно и тоже семейство языков.

Неизвестно, образуют ли классы языков главные АСЯ, т.к. неизвестно, можно ли для каждого автомата из построить эквивалентный не стоящий на месте автомат из ^^ . л

§ 6, Макрограмматики

Определение 01-макрограмматик [9] допускает следующее обобщение, Правила 01-макрограмматик можно считать функциями с текстовыми параметрами, использующими вызов по наименованию и единственную элементарную операцию-конкатенацию строк. Такие макрограмматики являются модель^ существующих текстовых макрогенераторов. Используя введенный в Алголе 68 тип данных-процедура с заданным ввдом параметров-можно расширить правила 01-макрограмматик, допустив в качестве параметров процедуры.

Определение 7. Элементы множества

Я* { ИЛИ ^ЙЬ., Тп)То| Т'^в или Т^ • £ К ив определении

71 не участвует Т > П^ О ♦ если гг. =0, то Т- То } называются видами. Уровень вида равен #+1, если в определении Т вложенность скобок равна К* В определении Т, То называется видом результата, а Тс -видами параметров.

Пример, Уровень вида ((, () ), () () ) () равен 3«

Пусть £ -терминальный алфавит, £ и 66 2 имеют вид £ , X = ипеременные (нетерминальный алфавит), У=Ц"Ут параметры Т -некоторое множество видов, £ € Т •

Термом над 21 1ГХиУ называется: либо элемент Л 17Х 1Г У параметров, либо вида То » где t -терм вида Тъ)Тоу ^-терш вида Тс , либо Ь^Ьг , хде

Н -термы, виды результатов которых равик 6 .

Определение 8. В вышеприведенных обозначениях 01-макрограм-матикой уровня К называется пятерка М& = <2:1Х7У?Р,^о > , те Р-набор правил У«)-* Л , для Хс€Х, Уи € У > терма Д/ , включающего из параметров только У I , Ун, , имеющего вид , Тк)То

•¿мен, такой* что ввд X ГТ , вид у^ равен Тс и вид ^ равен Т0» а

5 0 € X £ -начальная переменная. Уровень макрограмматики равен ( ф максимальному уровню видов для £иХ17У»

Шаг вывода в макрограмматике задается применением правила к переменной, т.е. Д *-0, если в терме А выделен подтерм имеется правило X ( У*)-» » и теРм В получен в результате замены в А выделенного подтерма; ва <Ь ( = Хс )-результат подстановки термов дЦ вместо параметров у^ в терм Ж • Вид результата терма А совпадает с видом терма 3. Слово ы выводимо в макрограмматике И & , если существует последовательность термов А^, А^ такая, что ¿>о н. Ал = .

Теорема 9. Для каждой индексной грамматики уровня К можно построить » эквивалентную макрограмматику уровня К.

• Доказательство. Предположим, что индексная грамматика приведена к нормальной форме (Лемма I) и её нетерминальный алфавит является разделенным, V = ЦУс *

Каждому нетерминалу X 6 Ус поставим в соответствие переменную Х( У1,.,Уа)г * -число символов в > и перемен-ные (2,Х) (Уц., Угг) Для всех ге , а также параметр У* .

Пусть У¡^-последовательность параметров, соответствующая нетерминалам I -того уровня в некотором порядке; обозначим её У № ,

I ф - И) а соответствующую последовательность нетерминалов через у] .

Каэдому правилу А ^ ВС (для Д уровня I > 1) поставим в соответствие макроправила А(уа>)-> В (У У^ С)( ,

Каддому правилу А — В° (для уровня С ) поставим в соответствие макроправила с),., (уО) (У«>) .

Для правила интерпретации I (Ав) » С поставим в соответствие 0 макроправило А( У) = У(^А)» ] (А)- номер параметра, соответствующего 4» и макроправило (А, В) ( У (0) С( у

Правилу А-*« ВС на уровне 1 поставим в соответствие макроправило — В( у*4>) С( У СО). Правилу А-»- 6 поставим в соответствие макроправило У . Правилу 3 поставим в соответствие макроправило $© £ .

Легко проверить» что указанное соответствие правил и макроправил задает соответствие выводимых многоэтажных выражений и выводимых термов. Причем каждому одночлену А2 соответствует терм

А( п)» эде Ж с -это терм, из которого выводимы тер мы, соответствующие многоэтажным выражениям,, выводимым из А ¡ , где А ¡, - i -тый нетерминал (на соответствующем уровне). При применении макроправил, соответствующих интерпретации, переменная заменяется на её параметр, номер которого равен номеру переменной» Таким образом, одноэтажные выражения выводимые в индексной грамматике, совпадают с термами без параметров в соответствующей ей макрограмматике, и, следовательно порождаемые ими языки также совпадают»

Теорема 10. Для кадцой макрограмматики уровня К можно построить ч эквивалентную макрограмматику уровня К в приведенной форме с правилами типа Р(.У1 "Ун)"-* (Уа',.»., УЧ),Нт(У4,.м,Уц)^

Уп Нт^+г,,., У к)) при т>0; , и к>о.

Yll)"♦^(Yí,.м)Ya)' Н(У1Г.„ Уи/)НА уровне 0, Р(У|,.,Уп>^ на уровне 0 или $с £ •

Доказательство. Устраним все правила А( У*,»., У к )"**£ , добавив для каждой совокупности вхождений А(2-1 ;.М) 2 ц ) в правую часть некоторого правила новое правило с заменой этих вхождений ^ на £ » Упорядочим у кавдой переменной параметры в соответствии с некоторым порядком на У по убыванию уровней видов. Устраним все правила А(У± У*) В( .«, Уа), добавив для каждой совокупности вховдений Д в правую часть некоторого правила новое правило с заменой этих вхождений А на В с соответствующей подстановкой параметров. Далее индукцией по уровню вида правила докажем, что любое правило можно заменить на набор приведенных правил, порождающих только правую часть заданного правила и тупики« При уровне правила I. (бесконтекстное правило-параметров нет) нормальная форма [¿2] набора правил типа г А—" б" или А—ВС ^ удовлетворяет условию теоремы. Пусть для правил уровня не больше I-теорема доказана*

Пусть У=Уц., У* » а Б -последовательность тупиковых переменных требуемых видов*

Рассмотрим правило Р (У уровня• При ("Ьа,,.^ -Ьпч} введем новую переменную £ и правила V^(</н . Пусть из & (У) выводимы УнУс2,с возможными параметрами (этот список можно построить конструктивно,: т.к. для макрограмматик разрешима проблема принадлежности [3}|и не выводимы остальные ^. Тогда заданное правило можно заменить на набор правил

Нт(у»,.„ р(у)^У^ниг),., Нм(?)),

РСУЬ&Сн/Д,.^ нм(у)), тае У = У^+А-, Уп, ("¿¡г зависит только от У^а,.»,Уит»к* параметры переменных упорядочены по убыванию уровней, а уровень вида переменной больше, чем уровень вида её параметров)^ Правило

И^ (у) £ » имеют уровень не больше ^ , поэтому его можно заменить на набор правил в приведенной форме, К правилу О-^Л^у^х>) нужно применить вышеприведенный процесс замен; этот процесс завершится, т.к. длина терма <¿1 меньше, чем длина терма об • При <1=$>')(<> и 6 * для уровня результата Я равного О, заменим правило на правила У и,)-* &(У1,.9 У*)* Н(У4г,.,Уи^? и к двум последним применим вышеприведенные замены; этот процесс замен завершится, т.к. длина термов ^ и ^ меньше длины об . При «1 = £ или об- Зо) правило в приведенной форме. Итак, во всех случаях правило заменяется на набор приведенный правил.

Теорема II. Для каждой макрограмматики НО уровня К можно построить эквивалентную индексную грамматику 0- уровня К .

Доказательство. Пусть Мб- в приведенной форме. Порождаемые приведенной макрограмматикой термы будем называть приведенными. Запишем каждый приведенный терм , „., -Ц щ)- ) в следующем виде ^(tty »ti м) где ч^ it, ЬС -бесскобочная запись последовательности приведенных термов, т.е. > (fyl, - fy*)iii^ilu 4 fy. >. K (jrn> применено аналогичное^ преобразование, в # -новый нетерминал, играющий роль маркера; здесь ( Ai. А ь - Ai . Аи. и (А< . А к)* A i. А к. Пусть Yi ., У к, -вектор параметров.

Каждое макроправило может быть заменено аа набор индексных правил которые осуществляют следующие преобразования:

1. Нъ(У)) осуществляет Р

2. Р(У)-> У1 (И1(У),н.)Йг^))осушествляет р . ¿к*,, Сг1'*«• С-* *

3. р(У)-* У с осуществляет Р > р(У) (г('У)'Н(У) осуществляет Р-"(г'Н ^

5- или £ осуществляет ¿оббили Р .

Для сшучаев 1,4 и 5 набор правил состоит из одного указанного правила.

ЗАКЛЮЧЕНИЕ

Данная диссертация посвящена сравнительному изучению средств описания языков и их анализа* Показано, что последовательность классов индексных языков заданного уровня имеет а естественное определение при различных подходах к заданию и анализу языков* Рассмотрены также грамматики Вейнгаардена, исполыовавшиеся для описания Алгола 68, и их соотношение с индексными грамматиками* Введенное в диссертации теоретические модели оказали влияние на разработку транслятора с Алгола 68 для МВК Эльбрус.

Основными этапами при выполнении диссертационной работы б|глиг следующие: введение новых обозначений для индексных грамматик; введение расширения индексных грамматик; доказательство неразрешимости алгоритмических проблем для индексных грамматик неограниченного уровня; доказательство \,^ разрешимости алгоритмических проблем для индексных грамматик конечных уровней и установление их свойств замкнутости; изучение многоуровневых магазинных автоматов и макрограмматик; установление разрешимости проблемы принадлежности для однозначных грамматик Вейнгаардена путем их моделирования индексными грамматиками уровня 3. В ряде доказательств существенным является использование нормальной формы;

Результаты диссертации получили дальнейшее развитие в ряде последующих публикаций. к*

Продолжение исследований

В статье М. Ванда [28] была также введена последовательность 5*кна основе теории категорий, однако существенных результатов т доказано не было.

В, Дамм также ввел последовательность ^ ^ в связи с изучением схем программ [29] . В этой и последующих работах [зо] он независимо от автора настоящей диссертации показал разрешимость проблемы принадлежности для многоуровневых языков, ив [31] он доказал строгую вложенность классов $ к.

Многоуровневые индексные языки с помощью макрограмматик введена и изучены независимо и в статьях Энгельфрита и Шмидта [32^

В статье Хаяши [п] и работе Боера [16] доказана лемма о двойном периоде для индексных языков.

В статье Майбаума [34*] изучаются индексные грамматики уровня 3, а в [35]ондал более простое доказательство леммы о двойном периоде для индексных языков.

В статье Энгельфрита я Скима [Зб] построен пример не индексного языка, который позволяет доказать, что класс однозначных грамматик Вейнгаардена не вложен в класс $ % индексная: грамматик (см. § 6).

Приведенный список работ показывает, что введенное в статьях автора расширение индексных грамматик находится в тесной Связи с другими математическими моделями. * Изложенные в диссертации результаты докладывались на семинарах в МГУ, ЛГУ, Институте математики СО АН СССР и: на симпозиуме [33]. Основные результаты опубликованы в [14, 15, 17] .

Автор признателен Э. Д. Стоцкому, A.A. Мучнику и Г.С. Цейтину за полезные замечания и обсуждения предварительных вариантов публикаций, Н.П. Трифонову за внимание к работе, Б.Н. Орлову и Е.К, Дегтяреву за поддержку на заключительном этапе написания дис-№ сертадии.

ЛЙЕЕРАТУРА

I* Chomsky If,, On the certain formal properties of grammars. Information and control, 1959, ¿,12, 137-167.

Русский перевод: Хомский H., О некоторых формальных свойствах грамматик. Кибернетический сб., вып. 5, ИЛ, 1962, 279-311 •

2. Cinsburg S., Rice I.e., Two families of languages related to ALGOL. J. Assoc. Comput. Machinery, 1962, 2,» 3,350

371.

Русский перевод: Гинзбург С., Райе X., Два класса языков типа АЛГОЛ, Кибернетический сб., новая серия, вып.6, "Мир", 1969.

3. Chomsky Н., Context-free grammars and pushdown storage. m.i.Т. Res. Lab.Ilectron.Quart.Prpg.aept. 65, 1962.

4>. Ever R.J., The theory and application of pushdown store machines.Mathematical Linguistic and Automatic Translation

H Harvard Univ.»Computation Lab.Kept. NS?2I0, May, 1963»

5. Маслов A.H., Стоцкий Э.Д., 0 некоторых классах формальных грамматик. "Теория вероятностей. Математическая статистика. Теоретическая кибернетика". (Итоги науки и техники) 1975, 155-187.

6. Патерсон М.С., Проблемы разрешимости в вычислительных моделях. В сб.: "Теория программирования. Ч. Iй, Новосибирск, 1972, II9-I36.

7. Aho А.V., Indexed grammars - an extention of context--free grammars.J.Assoc.Comput.Machinery,1968.15.N"4,647-671. jp. Русский перевод: сб.: "Языки и автоматы", М., "Мир", 1975 .

8. Aho A.V., Nested stack automata.J. Assoc. Comput. Machinery, 1969, 16, H 3, 383-406.

9* Fischer M.J., Grammars with macrolike productions. ?h.j Dissert., Harvard Univers., I968. (Report HSF-22, The Computational Laboratory of Harvard University, 1968).

10. Sounds W.C., Mappings and grammars on tress. Math.Syst Theor., 1970, 4,

11. Xayashi Т., On derivation trees of indexed grammars, in extension of the uvwxy-theorem. Pubis. Res* bast. Sci., 1975, 9, Ш I, 61-92p

12. Гладкий А.В., Диковский А.Я., Теория формальных грамматик. "Теория вероятностей. Математическая статистика. Теоретическая кибернетика". (Итоги науки и техники) 1972; 10, 107-142»

13. Sintsoff М., Existence of а van Wijngaarden syntax for every recursively enumerable set. Ann. Soc. Scient. Bruxelles 1967, Ser. 1, 8Ij №2, II5-XI8.

14. Маслов A.H., Индексные грамматики и грамматики Вейн-гаардена. Проблемы передачи информации, 1975, вып.3, 81-89.

15. Маслов А.Н., Иерархия индексных языков произвольного уровня. Докл. АН СССР, 1974, 217. Ш 5, I0I3-I0I6.

16. Боер А.Ф., 0 некоторых свойствах индексных и условных грамматик. Дипломная работа. Кафедра математической логики, МГУ, 1974»

17. Маслов А»Н., Многоуровневые магазинные автоматы. Проблемы передачи информации, 1976, вшг.1, 55-62.

18. Qreibach S.A., Chains of full AFX*'е., Math« Syet. Theo: 1970, Ж 3, 231-2*2.

19» einsburg s., Greibach S.A., Abstract families of languages* Mem. Amer. Math. Soc., 1969, £1 87, 1-32. Русский перевод: сб., "Языки и автоматы", М., "Мир", 1975 .

20. Маслов А.Н., Аксиоматический-подход к описанию систем

Актуальные вопросы с управлением. Сб. теории множеств и математической логики , МГПИ, 1975, 128-138.

21. Гинзбург С.; Математическая теория контекстно-сво-бодных языков. М., "Мир", 1970.

22. Гладкий А.В., Формальные грамматики и языки. М.; "Мир", 1973.

23»tfijngaard*n a. van, Mailloux В-J., feck J.K.L., Koster C.U.A., Report on the algorithmic language ALGOL 68., Burner. Math., 1969, W. 79-218.

Русский перевод: журн. Кибернетика, 1969, ft 6 и 1970, Jfe I

24. Wijngaarden A. Tan. Mailloux S.J., Peak J.S.L., Koster С.И.A., Sintaoff U., Lindeey C.I., Meertene L.G.L.®.,

Jleker R.G., Revised report on the algorithmic language

ALGOL 68., 1974, (Приложение к "ALGOL-lulletin" N-36, 1973)

226 c.

25. Hum M., A machine-Independent theory of the oomple*» xity of recursive functions., J.Assoc. Machinery, 1967, I£, H 2, 322-336.

- w

Русский перевод: сборник аПроблемы математической логики", v —

М., «Мир«, 1970, 401-422.

26. Стоцкий Э.Д., Формальные грамматики и ограничения ид вывод. Проблемы передачи информации, 1971, 7, te i, 87-101.

27. Ломковская М.В., 0 некоторых свойствах К- условных грамматик. Hayчн.-техн.информ.Всес.ин-т науч. и техн.информ. 1972; сер. 2, to I, 16-21, 32.

28. Wand M., An algebraic formulation of the Chomskj^.-hierarchy, category theory applied to computation and control.»Lect. Motes in Comput. Soil«, 1975, 25, 209-213^

29. Damm llf., Languages defined by higher type program schemes. "Proc. 4th Int. Coll. on Automata, Languages and Progr., Lect. Notes in Comput.Sci.1977, 52, 164-179,

30. Damm W., Pehr В., Indenmark K., Higher type re$td&3ion and self-application as control structures. "Proc.Ii4p Work СояПУРогт.Description progr.Lang.", 1978, 461-489.

31. Damm W., An algebraic extension of the Chomsky- hierarchy. "Lect.Notes Comput.Sci, 1979, 74, 266-276.

32. Engelfriet J., Schmidt B.M. 10 and 01. Part 1 and 2. "Jorn.Cogput. and Syst.Sci.», 1977, 15, Ш3, 328-352j

1978, 16, NM, 67-99.

33» Маслов A.H., Использовав« расширения индексных грамматик доя синтаксического анализа, "Тр„ Вове* Симп. по методам реализ. нов. алгоритм, яз. Ч. 2*. Новосибирск, 1975, 202-Й0Э,

34. Maihaum T.S.B.,A generalized approach to formal languages. "J.Comput.Syst.Sci.», 1974, J409-439.

35. Maibaum I.S.B., Pumping lemmas for term languages. "J. Comput. and Syst.Sci.«, 1978, 17, 319-330,

36. Engelfriet J., Skyum S., Copying theorems. "Inf.Process. Lett.», 1976, 4, N5 6, 157-161.

37* Бредь В.В.£расмов, Маслов А.Н», Язык программирования АЛГОЛ 68. "Теория вероятностей-Математичвекая статистика Теоретическая кибернетика (Итоги науки и техн. ВШДОГИ АН СССР)". М., 1979, 15, Е

ЩМЫСМНЛТС

Рис. I. Промежуточному слову вывода соответствует указанная конфигурация автомата

Рис. 2. Состояние памяти в следующий момент равно » а состояние программы равно |э' , если р' удовлетворяет отношению , 7.

0 Г ДАВЛЕНИЕ

Стр.

Введение . 2

§ I. Определение классов ^порождающих грамматик 12

§ 2. Основные свойства классов .16

§ 5* Связь с грамматиками Вейнгаардена . 28

§ 4. Многоуровневые магазинные автоматы . 40

§ 5. Свойства замкнутости. Системы допускающих ав- 50 томатов .

§ 6. Макрограммачгики .60

Вбвзшодшге . . 66

Литература 69 г