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

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

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

/ Л—7

ь

004603847 Сутырин Павел Георгиевич

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

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

1 О ИЮН 2010

Москва — 2010

004603847

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

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

профессор М.Г. Мальковский.

Официальные оппоненты: доктор физико-математических наук,

профессор Р.И. Подловченко

доктор физико-математических наук, профессор Б.Ф. Мельников

Ведущая организация: Вычислительный центр

им. А. А. Дородницына Российской академии наук.

Защита диссертации состоится 28 мая 2010 года в 11.00 иа заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу. 119991, ГСП-1, Москва, Ленинские горы, МГУ, второй учебный корпус, факультет вычислительной математики и кибернетики, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ http://cs.msu.ru в разделе "Наука" — 'Работа диссертационных советов" — "Д 501.001.44".

Автореферат диссертации разослан " апреля 2010 года.

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

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

Общая характеристика работы

Актуальность темы

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

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

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

Известно, что проблема регулярности разрешима для подкласса детерминированных КС-языков, допускаемых детерминированными магазинными автоматами. При этом большое значение имеет поиск для нее практически применимых алгоритмов.

Разрешимость проблемы эквивалентности также доказана для детерминированных магазинных автоматов. Однако, имеющиеся доказательства (в. Зешге^иев, 1997, В. Мейтус. 1992) являются чрезвычайно громоздкими и сложными для понимания, что заставляет искать более компактное и естественное решение.

Введенные в работах Л.И. Станевичене Б-графы1 представляют собой новый способ описания КС-языков. Их прообразами являются графы .магазинных автоматов. Б-графы — более удобный инструмент исследования многих свойств КС-языков, чем магазинные автоматы и КС-грамматики. Так, с помощью Б-графов было построено более простое доказательство теоремы Хомского-Шютценберже о морфическом представлении КС-языка.

1 Станевичене Л.И. К теории бесконтекстных языков. М.: МГУ им. М.В. Ломоносова. 2000. Деп. в ВИНИТИ 29.05.2000. № 1546-В00.

Цель работы

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

Задачи работы

1. Применить аппарат Б-графов к исследованию регулярных языков, исследовать задачу о звездной высоте с использованием теории графов.

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

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

Методы исследования

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

Научная новизна и основные результаты

Основные результаты диссертации являются новыми, получены автором самостоятельно и состоят в следующем:

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

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

Данный алгоритм строит выражения меньшей сложности, чем известные алгоритмы. Выделен подкласс графовых описаний, для которых предложенный алгоритм дает решение задачи о звездной высоте.

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

4. Для подкласса графовых описаний с однозначной парностью на основе алгоритма проверки эквивалентности построена система эквивалентных преобразований и доказана ее полнота в этом классе.

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

Теоретическая и практическая значимость

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

Апробация работы

Результаты научных исследований были представлены на Международной конференции "Mathematical Modeling and Computational Physics" (Дубна, 2009), двух Международных научно-практических интернет-конференциях "Современные направления теоретических и прикладных ис-следований'2009" и "Научные исследования и их практическое применение. Современное состояние и пути развития'2009", научных конференциях МГУ "Ломоносовские чтения" и 'Тихоновские чтения" (2009), а также на научно-исследовательских семинарах в МГУ имени М.В. Ломоносова и Вычислительном центре им. А.А. Дородницына РАН (2010).

Публикации

По теме диссертации опубликовано 6 работ.

Структура и объем диссертации

Работа состоит из введения, 6 глав, заключения и списка литературы, содержащего 52 наименования. Общий объем работы составляет 117 страниц.

Краткое содержание диссертации

Во введении обосновывается актуальность работы, формулируется цель и задачи исследования.

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

Б-множеством называется подмножество V декартова произведения А] х Лг непустых непересекающихся алфавита А\ открывающих и алфавита А2 закрывающих скобочных символов, оно задает парность между скобками.

Пусть Е — непустой алфавит терминальных символов, в который не входит символ е. Графовым описанием (ГО) над алфавитом Е называется семерка

где V — непустое множество вершин, Е = {(-и/и) | и,у £ V} — множество ориентированных дуг, V — Б-миожество, А : Е ~> (Е и {е}) х (Аг и А2) — функция пометки дуги, значение которой есть пара из терминальной и скобочной пометок, € V — начальная вершина, Е СУ- множество заключительных вершин. Для каждог о пути Т в графе (V, Е) определяются его терминальная пометка ш(Т) — цепочка в алфавите Е, составленная из терминальных пометок соответствующих дуг, и скобочная пометка ж(Т) — цепочка в алфавите А\ и Аг, аналогичным образом полученная из скобочных пометок дуг. Предложением графового описания С называется такой его путь из начальной вершины в одну из заключительных, скобочная пометка которого образует правильную скобочную систему в Б-множестве V. Пути в (7, являющиеся фрагментами предложений, будем называть маршрутами. Множество всех предложений ГО С обозначим через 5'еп£еш!е,ч(С). Язык, задаваемый графовым описанием О есть множество всех цепочек в алфавите Е, являющихся терминальными пометками предложений (?, т.е.

Цв) = {и{Т)\Т£ Зепгепсев(в)}.

Два графовых описания Gi и CU называются эквивалентными, если

ОД) = ОД).

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

Отличие графового описания от D-графа состоит в выделении в явном виде пары (V, Е) как основы графа и введении двойной пометки дуги. Кроме того, рассмотрение D-множеств с нейтральным элементом позволяет получить конечный автомат как простой частный случай графового описания.

На множестве маршрутов графового описания определяется отношение развития. Оно аналогично отношению развития, определенному для маршрутов D-графа и выражает возможность получения сложных маршрутов из более простых (т.е., их развития) посредством включения в них новых фрагментов.

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

Форманты бывают двух видов — форманты-циклы и форманты-гнезда.

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

Формант-гнездо представляет собой тройку (Ть Тг, Т3), где Т2 есть нейтральный путь, a Ti и Т'2 — циклические пути, скобочные пометки которых являются парными друг другу (поэтому и сами эти циклы называются парными). Это позволяет па основе произвольного числа согласованных (одновременных) итераций парных циклов получать более сложные предложения из любых предложений, содержащих данный формант.

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

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

Определение. Графовое описание С будем называть детерминированным, если для каждой вершины и £ У(С) множество дуг Е' — {(и, г») £ Е(С)} обладает следующим свойством: если Е' содержит более одной дуги. то либо Уе1,е2 £ Е' выполняется 7г(ех) £ Аг, 7г(е2) 6 Ах и и{ех) ф ш(е2), либо \/в!,е2 £ Е' выполняется и{ех) £ А2, тг(е2) £ А2 и не существует ох £ Ах такого, что (ах, 7г(е1)) £ V и (а^ 7г(ег)) £ V.

Теорема 1.2. Класс языков, задаваемых детерминированными графовыми описаниями, совпадает с классом детерминированных бесконтекстных языков.

Определение. Графовым описанием с однозначной парностью будем называть ГО (7, такое, что для любой его дуги е, такой что 7г(е) £ Ах, существует не более одной дуги е', такой что тт(е') £ А2 и (7г(е), 7г(е')) £ V.

Теорема 1.3. Класс языков, задаваемых графовыми описаниями с однозначной парностью, в точности совпадает с классом ЬЬ(1)-языков.

Теорема 1.4. Если ГО С? не содержит формантов-гнезд, то язык Ь{С) является регулярным.

Памятью графового описания С? будем называть пару р = (еп<1(Т), Т"), где Т" £ гейисИоп(Т) для некоторого префикса Т предложения ТТ' £ ,5еп1епсез(С). Множество всех памятей ГО О будем обозначать как

Мет(С) = {(епй(Т),Т") | ВТ': ТТ' £ Зегйепсе8(С),Т" € гв(1исМоп(Т)}.

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

Теорема 1.4 Множество Мет(С) всех памятей ГО С является регулярным.

В главе 2 рассматривается подкласс графовых описаний, задающих регулярные языки. Дается обзор существующих алгоритмов анализа конечных автоматов и построения эквивалентных регулярных выражений (С. Клини (1956), Д. Вуд (1987), Б. Ф. Мельников, А. А. Вахитова (1998)) Предлагается новый алгоритм СяарнОебс-То-ПесЕхрк преобразования графового описания, задающего регулярный язык, в регулярное выражение.

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

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

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

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

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

Теорема 2.1. Алгоритм GraphDesc-To-RegExpr является корректным. Звездная высота получаемого регулярного выражения равна циклическое глубине иерархического графа.

Теорема 2.2. Алгоритм GraphDesc-To-RegExpr имеет временную сложность 0(|Е|!), где Е есть множество дуг графового описания.

Производится сравнение предложенного алгоритма с существующими, показывающее уменьшение таких характеристик получаемого регулярного выражения, как звездная высота и длина. Так, для графового описания, состоящего из одной вершины и имеющего на ней циклы с пометками aj, «г. • ■ • an все известные алгоритмы строят выражения вида o,i(аг(... а* )*.. .)* звездной высоты п, тогда как алгоритм GraphDesc-To-RegExpr строит выражение (ai + ai... + an)* звездной высоты 1.

Рассмотрим также графовое описание С без циклов, имеющее точку сочленения, соединяющую два его фрагмента Gj и G-z, с числом предложений в них mi и W-2 соответственно. Число предложений ГО G есть mi то, и существующие алгоритмы строят регулярное выражение с числом слагаемых порядка тщт2, тогда как алгоритм GraphDesc-To-RegExpr строит выражение с числом слагаемых порядка т\ + то-

Теорема 2.3. В классе графовых описаний с попарно различными терминальными пометками на дугах алгоритм GraphDesc-To-RegExpr строит эквивалентное регулярное выражение минимально возможной звездной высоты, т.е. дает решение задачи о звездной высоте регулярного языка.

В главе 3 рассматривается проблема регулярности для графовых описаний. R. Stearns (1967) и L. Valiant (1975) получили доказательства раз-

решимости проблемы регулярности для детерминированных бесконтекстных языков. Однако эти доказательства весьма громоздки, что заставляет искать более компактные доказательства. Подклассы детерминированных магазинных автоматов, задающих регулярные языки рассматривались А.А. Вылитком (1998). Решение проблемы регулярности для т.н. праволинейных детерминированных магазинных автоматов было предложено Л.И. Станевичене (2000).

В настоящей работе предлагается решение проблемы регулярности для подкласса LL(1)-языков, которое опирается на анализ памятей и формантов графовых описаний.

Теорема 3.1. Язык, задаваемый графовым описанием G, тогда и только тогда является регулярным, когда отношение эквивалентности на множестве памятей Mern(G) имеет конечный индекс.

Теорема 3.2. Для того, чтобы язык, задаваемый детерминированным графовым описанием G с однозначной парностью, являлся регулярным, необходимо и достаточно, чтобы в нем не было ни одного форманта-гнезда (2\,Т2,Тз), такого что одновременно w(Ti) ф Л и w(T3) ф Л.

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

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

Теорема 3.3. Алгоритм regularity является корректным.

Теорема 3.4. Алгоритм Regularity, применяемый к графовому описанию G, имеет временную сложность 0{\Р\^), где V есть D-множество ГО G, а Е — множество дуг G.

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

В главе 4 рассматривается проблема эквивалентности для детерминированных графовых описаиий. Дается обзор существующих решений. Доказательства разрешимости проблемы эквивалентности для детерминированных бескоитекстпых языков были построены В. Мейтусом (1992) и G. Senizergues (1997), однако эти доказательства громоздки и содержат неясные места. Известны доказательства разрешимости проблемы эквивалентности для подклассов детерминированных бесконтекстных языков: Зубенко (1978), Романовский (1980), Непомнящая (1981), Мейтус (1989), Анисимов (1997), Станевичене (2000).

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

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

Теорема 4.2. Задача построения графа сопряжения для детерминированных графовых описаний является алгоритмически неразрешимой.

Показывается разрешимость этой задачи в классе детерминированных ГО с однозначной парностью, предлагается алгоритм Equivalence ее решения и исследуются его свойства:

Теорема 4.3. Алгоритм Equivalence является корректным.

Теорема 4.4. Алгоритм Equivalence, применяемый к графовым описаниям Gi и G2 имеет временную сложность

0{max(\Vi! + \Eî\, \Р2\ +

где Vi есть D-множество графового описания Gi, a Ei — множество дуг Gi, г = 1,2.

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

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

Преобразованием графовых описаний является любая их пара (Gi, G2)-Преобразование (Gi,G2) называется эквивалентным, если G1 ~ G2- Для множества (системы) Т эквивалентных преобразований вводится понятие замыкания Г, определяемое следующим образом. Пара ГО (G'^G^) при-

надлежит Т тогда и только тогда, когда существует последовательность

{Gi,G2)){GÏ, G 3),..., {Gk-1, Gk)

преобразований из Т, для которой G[ = Gj и G'2 = G%. Система эквивалентных преобразований Т называется полной в некотором классе графовых описаний, если любое эквивалентное преобразование графовых описаний этого подкласса принадлежит замыканию Т.

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

Отметим, что сама идея построения полной системы с использованием алгоритма проверки эквивалентности была высказана (устно) Р.И. Под-ловченко в 2010 году.

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

В процессе анализа алгоритма Equivalence получены следующие классы эквивалентных фрагментов.

Класс Ыпеаг, "линейные" содержит все пары линейных фрагментов графовых описаний, имеющих бесцикловую структуру.

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

Класс PairCycles, "парные циклы", содержат все пары фрагментов, содержащих формант-гнездо, и получаемых друг из друга аналогичным вынесением и включением линейных маршрутов, а также аналогичной кратной итерацией.

На основе эквивалентных преобразований, соответствующим указанным классам фрагментов, строится система То-

Теорема 5.1 Система Т0 эквивалентных преобразований графовых описаний является полной в классе детерминированных графовых описаний с однозначной парностью.

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

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

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

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

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

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

Публикации по теме диссертации

1. Сутырин П.Г. Алгоритм построения регулярного выражения по конечному автомату // Сборник тезисов лучших дипломных работ 2006 года. — М.: Издательский отдел Факультета ВМиК МГУ, 2006- С. 94-95.

2. Сутырин П.Г., Мальковский М.Г. Иерархические конечные автоматы и звездная высота регулярных выражений / / Программные системы и инструменты: Тематический сборник / Под ред. Королева JT.H. - М.: Издательский отдел ф-та ВМиК МГУ, 2008. № 9. - С. 32-49.

3. Мальковский М.Г., Сутырин П.Г. О задачах преобразования описаний формальных языков // Сборник научных трудов международной научно-практической конференции "Современные направления теоретических и прикладных исследований'2009". — Одесса: Изд-во Черноморье, 2009. Том 2. - С. 15-18.

4. Сутырин П.Г. Об инструментальных средствах теории формальных языков // Сборник научных трудов по материалам международной научно-практической конференции "Научные исследования и их практическое применение. Современное состояние и пути развитгч '2009". — Одесса: Изд-во Черноморье, 2009. Том 16. — С. 7-9.

5. Вылиток A.A., Сутырин П.Г., Харченков С.Л., Юдочев Д.В. О сопряжениях графовых описаний формальных языков // Программные системы и инструменты. Тематический сборник / Под ред. Королева Л.Н. — М.: Издательский отдел Факультета ВМиК МГУ, 2009. № 10. - С. 91-99.

6. Сутырин П.Г. О множестве памятей D-графа // Вестн. Моск. Ун-та, Сер. 15, Вычисл. матем. и кибернетика, 2010. № 1. — С. 45-51.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 26.04.2010 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 193. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.