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

I О <■ /

1 ? 7 ¡1 Московский государственный университет

имени М.В. Ломоносова Факультет вычислительной математики и кибернетики

Маслов Александр Николаевич

Расширение класса индексных языков

Специальность 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—о^), если существует последовательность слов ос = ^ такая, ЧТО либо - Лля некоторого |>€р , либо

получается из заменой некоторого вхожде�