автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Магазинные автоматы и характеризация регулярных языков

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

п *- ^ п

На правах рукописи

1 1 СЕН 199В УДК 519.682.1+510.53

Вылиток Алексей Александрович

Магазинные автоматы и характеризация регулярных языков

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и сетей.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1998

Работа выполнена на кафедре алгоритмических языков факультета Вычислительной математики и кибернетики Московского Государственного Университета им. М.В.Ломоносова

Научный руководитель: кандидат физико-математических наук

Официальные оппоненты:

доктор физико-математических наук Серебряков В.А. кандидат физико-математических наук Миронова И.В.

Ведущая организация:

Институт системного программирования РАН

Защита диссертации состоится "9 " октября 1998 года в II00 в ауд. 685 2-го уч. корпуса на заседании диссертационного совета Д 053.05.38

при факультете Вычислительной математики и кибернетики МГУ по адресу: 119899, ГСП, Воробьевы горы, МГУ, факультет ВМиК.

С диссертацией можно ознакомиться в библиотеке факультета.

Станевичене Л.И.

Автореферат разослан

Ученый секретарь диссертационного совета,

профессор

Н.П. Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

* •

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

Научная новизна. В терминах теории Б-графов определяется подкласс магазинных автоматов, названных автоматами без самовставления. Доказывается, что он характеризует регулярные языки. Принадлежность автомата данному классу распознаваема, что дает нетривиальное достаточное условие регулярности бесконтекстного языка.

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

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

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

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

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

Апробация работы. Результаты диссертационной работы докладывались на Третьей международной конференции по алгебре (Красноярск, 1993), научно-исследовательском семинаре по автоматизации программирования (факультет ВМиК МГУ, март 1998).

Публикации. По теме диссертации имеется 3 публикации, список которых приводится в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, одного вспомогательного и трех основных разделов и списка литературы. Общий объем диссертации — 79 страниц. Библиография включает 53 наименования.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В разделе О приводятся понятия и факты теории Б-графов, используемые в основных разделах данной работы. Понятие Б-графа тесно связано с понятием Б-языка, которое определяется в разделе 0.1. Раздел 0.2 содержит определение Б-графа и представленного им языка. Класс языков, представимых Б-графами, совпадает с классом бесконтекстных языков.

Одним из важнейших в системе понятий, основанной на "Б-графической" интерпретации бесконтекстных языков, является

з

понятие ядра, которое вводится в разделе 0.3. Ядро представляет собой некоторое конечное подмножество путей на Б-графе. Оно выделяет конечное подмножество представимого Б-графом языка, "разрастанием" цепочек которого получаются все остальные цепочки языка. В терминах ядра удобно формулируется так называемая история разрастания, или развития, данной цепочки из некоторой цепочки, выделяемой ядром.

Раздел 0.4 дает способ построения по любому заданному магазинному автомату эквивалентного Б-графа (графа магазинного автомата) и определяет в терминах Б-графов понятия однозначности и детерминированности. Ядро Б-графа, построенного по магазинному автомату М указанным способом, называется ядром магазинного автомата и обозначается Соге(М).

В разделе 1 описывается более экономный, чем рассмотренный в разделе 0, способ построения ядра магазинного автомата.

Введенное в разделе 1.1 понятие элементарной схемы определяет простейший вид вычислений магазинного автомата. Некоторое конечное множество таких вычислений названо базой автомата. Из определения базы следует и способ ее построения.

Базу магазинного автомата М можно считать другим определением понятия ядра автомата, поскольку она, аналогично множеству Соге(М), дает материал для построения всех вычислений над цепочками языка. Последнее замечание справедливо в силу теорем 2 и 3 раздела 1.

Раздел 1.2 вводит отношение правого развития на множестве вычислений. Отношение правого развития позволяет более дисциплинированно, чем отношение развития, определенное в разделе 0, строить вычисления автомата из материала, предоставляемого ядром.

В разделе 2 предлагается оригинальный алгоритм построения грамматики, эквивалентной магазинному автомату, следствиями которого являются важные факты о взаимосвязи классификаций магазинных автоматов и бесконтекстных грамматик. Здесь не только исследуется взаимосвязь подклассов, известных по классическим работам. Выделяется обширный, ранее не изучавшийся класс магазинных автоматов, который в определенной мере аналогичен классу бесконтекстных грамматик без самовставления.

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

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

да в бесконтекстной грамматике.

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

В разделе 2.3 приводится новое доказательство того, что язык, допускаемый детерминированным магазинным автоматом, является Ы1(1)-языком. Это доказательство, по-видимому, более прозрачно, чем известные рал ее.

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

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

б

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1. Получен более экономный, чем известные ранее, способ построения ядра магазинного автомата.

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

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

Список литературы

1. Вылиток A.A. О построении графа магазинного автомата // Вестн. моек, ун-та. Сер.15, вычисл. матем. и киберн.1996. N 3. С. 68-73.

2. Вылиток А.А.,Стадевичене Л.И.,Чернцов И.В. D-графы в теории магазинных автоматов. М., 1996, 62 с. Деп. в ВИНИТИ 23.12.96, N 3730-В96.

3. Станевичене Л.И., Вылиток A.A. Один важный подкласс алгебраических языков // Третья междунар. конф. по алгебре: Тез. докл. Красноярск, 1993. С. 315-316.