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

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

005060396

Зубова Мария Анатольевна

ПРИМЕНЕНИЕ УНИВЕРСАЛЬНОГО КОНЕЧНОГО АВТОМАТА В ПРИКЛАДНЫХ ЗАДАЧАХ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ

05.13.18 - математическое моделирование, численные методы и комплексы программ

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

3 О МАП 2013

Ульяновск -2013

005060396

Работа выполнена на кафедре «Прикладная математика и информатика» в ФГБОУ ВПО «Тольяггинский государственный университет»

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

ФГБОУ ВПО «Тольятгинский государственный университет», профессор кафедры прикладной математики и информатики

Мельников Борис Феликсович

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

доктор физико-математических наук, профессор, Государственное научное бюджетное учреждение «Академия наук Республики Татарстан», директор института информатики

Аблаев Фарнд Мансурович

кандидат физико-математических наук, ФГБОУ ВПО «Саратовский государственный университет имени Н.Г. Чернышевского», доцент кафедры математической кибернетики и компьютерных наук Богомолов Алексей Сергеевич

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

ФГБОУ ВПО «Пензенский государственный университет»

Защита диссертации состоится 20 июня 2013 года в 13:30 на заседании диссертационного совета Д 212.278.02 при Ульяновском государственном университете по адресу: 432000, г. Ульяновск, ул. Набережная реки Свияги, 106, корп. 1, ауд. 703.

С диссертацией можно ознакомиться в библиотеке Ульяновского государственного университета, с авторефератом - на сайте http://uni.ulsu.ru и на сайте Высшей аттестационной комиссии при Министерстве образования и науки Российской Федерации — http://vak.ed.gov.ru.

Отзывы на автореферат в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 432017, г. Ульяновск, ул. Л. Толстого, 42, ФГБОУ ВПО «Ульяновский государственный университет», отдел послевузовского профессионального образования.

Автореферат разослан «_» мая 2013 года.

Учёный секретарь

диссертационного совета Д 212.278.02 кандидат физико-математических наук, доцент

М.А.Волков

1. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

Пик интереса к конечным автоматам Рабина-Скотта (или Медведева) пришёлся на середину прошлого века. Именно тогда и появились почти все самые важные и фундаментальные работы в этой области. Но вскоре интерес начал спадать и почти сошёл на нет примерно в начале 1970-х годов - с развитием теории детерминированных конечных автоматов. Учёные и исследователи было решили, что область изучена полностью и практически не содержит нерешённых задач1, но потом обнаружилось, что конечные автоматы могут быть применены для решения проблем из смежных наук. В рамках решения таких проблем способ представления языка часто оказывается важнее самого языка. Например, чтобы язык занимал как можно меньше памяти при хранении в вычислительном устройстве, из множества автоматов, задающих данный язык, необходимо найти минимальный по числу состояний.

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

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

Недетерминированные конечные автоматы впервые были рассмотрены в середине прошлого века Ю. Медведевым2, а также М. Рабином и Д. Скоттом3. Позднее, прежде всего при применении НКА к решению различных приклад-

1 В 1979 г. Бжозовски на Международном симпозиуме по теории формальных языков перечислил только несколько важных нерешённых задач: Briozowski J. A. Open problems about regular languages // Formal languages Theory: perspectives and open problems, R.V. Book (ed.). New York: Academic Press, 1980. P. 23-47.

" Медведев Ю.И. О классе событий, допускающих представления в конечном автомате // М.: Иностранная Литература, 1956. С. 385-401.

3 Rabin М О., Scott D. Finite automata and their decision problems // IBM J. of Research and Development.

1959. 3(2). P. 114-125.

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

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

Универсальный автомат за последние полвека описывался во многих работах, хотя до сих пор остаётся открытым вопрос, кто именно является его актором. Авторы одной известной статьи8 приписывают авторство К. Каррезу, ссылаясь на его отчёт9, который, однако, так и не был опубликован. Приблизительно в то же время Т. Камеда и П. Вейнер в своей работе10 описали объект, который, как впоследствии выяснилось, есть не что иное, как универсальный автомат. Немного позже, и не в контексте проблем, которые обсуждались в упомянутых работах, Дж. Конвей" предложил определение автомага, который тоже оказался универсальным.

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

- при этом, в отличие от бинарного отношения #, является полным инвариан-

4 Miller G.A., Chomsky N. Finitaiy models oflanguage users. In R.D.Luce, R Bush, and E. Galanter (eds.) ii Handbook of Mathematical Psychology. New York: Wiley, 1963. 2 (13). P. 419-492.

Greibach S. The Unsolvability of the Recognition of Linear Context-Free Languages И Journal of the ACM 1966. 13 (4). P. 471-629.

Ахо А., Сети P., Ульман Д. Компиляторы: принципы, технолог™ и инструменты. М.: Изд. дом «Вильяме», 2001. 768 с.

6 Mealy G.H. A Method for Synthesizing Sequential Circuits // Bell Systems Technical Journal 1955 Vol 34, No. 5. P. 1045-1079.

7 Moore E. F. Gedanken-experiments on Sequential Machines II Automata Studies, Annals of Mathematical Studies. Princeton: Princeton University Press, 1956. 34. P. 129-153.

Arnold A., Dicky A., Nivat M. A note about minimal nondeterministic automata // Bulletin of the EATCS 1992. 47. P. 166-169.

5 On the minimal ization of nondeterministic automaton: technical report / Computing Laboratory of the Science Faculty of Lille University; doer: Carrez C. - 1970.

Kameda Т., Weiner P. On the state minimization of nondeterministic finite automata // IEEE Trans. Computers. 1970. 19(7). P. 617-627.

" Conway J.H. Regular Algebra and Finite Machines. London: Chapman and Hall, 1971. 147 p.

- Определения этих объектов можно найти, например, в монографии: Мельников Б.Ф. Недетерминированные конечные автоматы. Тольятти: Изд-во ТГУ, 2009. 160 с.

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

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

Целью работы является создание алгоритмов решения различных прикладных задач теории формальных языков с использованием универсального автомата Конвея.

Основные задачи исследования:

1) описание вариантов определения универсального автомата;

2) доказательство совпадения автомата СОМ с универсальным автоматом;

3) исследование свойств автомата СОМ, следующих из его определения;

4) создание практических алгоритмов решения прикладных задач теории формальных языков с использованием универсального автомата;

5) описание применения расширенных вариантов автомата СОМ для определения различных вариантов описания подклассов класса контекстно-свободных языков;

6) описание применения автомата СОМ для решения некоторых задач, связанных с созданием эффективных математических моделей в экономике;

7) применение современных инструментальных средств разработки про-

13 Melnikov В., Vakhitova A. Some more on the finite automata // J. of Applied Math, and Computing (The Korean J. of Computational and Applied Math.). 1998. 5(3). P. 495-506.

граммного обеспечения, в том числе средств объектно-ориентированного программирования.

Объектом исследования являются недетерминированные конечные автоматы Рабина-Скотта (Медведева), в частности - универсальный автомат Конвея.

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

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

В работе использованы:

• методы доказательства теорем дискретной математики;

• математические методы разработки алгоритмов;

• математическое моделирование;

• современные методы создания программного обеспечения, объектно-ориентированное программирование.

Результаты исследования

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

Научная новизна

Доказано совпадение автомата СОМ и универсального автомага Конвея. Алгоритм построения автомата СОМ получен с помощью более простых для реализации алгоритмов, чем описанные ранее «алгебраические» алгоритмы построения совпадающего с ним универсального автомата. Вследствие этого алгоритмы работы с недетерминированными конечными автоматами (в частности, алгоритмы их эквивалентного преобразования14), получаемые на основе определения автомата СОМ, более просты для реализации, чем алгоритмы, получаемые на основе определения универсального автомата.

Практическая значимость исследования

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

14 См. Мельников Б.Ф., Сайфуллина М.Р. О некоторых алгоритмах эквивалентного преобразования недетерминированных конечных автоматов // Известия вузов. Математика, 2009, № 4, 67-71 и мн.др.

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

Достоверность результатов

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

Основные положения, выносимые на защиту

1. Определение автомата СОМ и описание модели работы произвольного конечного автомата на основе автомата СОМ.

2. Исследование свойств автомата СОМ, следующие из его определения, и доказательство совпадения автомата СОМ с универсальным автоматом.

3. Алгоритмы решения прикладных задач теории формальных языков с использованием универсального автомата.

4. Модели, расширяющие класс конечных автоматов, и применение в них автомата СОМ для описания специальных подклассов класса КС-языков.

5. Вычислительные методы и алгоритмы минимизации автоматов с помощью автомата СОМ. Их применение для упрощения специальных математических моделей, сводящихся к НКА.

6. Программный комплекс, включающий построение автомата СОМ и реализацию рассматриваемых в диссертации прикладных задач, применяющих этот автомат.

Апробация результатов исследования

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

• конференциях «Студенческие дни науки» Тольяттинского государственного университета (2010 г. и 2011 г.);

• Всероссийском конкурсе научно-исследовательских работ студентов и аспирантов в области информатики и информационных технологий в рамках Всероссийского фестиваля науки (Белгород, 2011 г.);

• конкурсе на лучшую научную работу студентов по естественным наукам Тольяттинского государственного университета (2011 г.);

• научных семинарах кафедры прикладной математика и информатики Толь-

ятгинского государственного университета (2009-2013);

• научном семинаре факультета математики и информационных технологий Ульяновсюго государственного университета (2012);

• I Международной научно-практической конференции «Научная дискуссия: вопросы м*гематики, физики, химии, биологии» (Москва, 2013 г.);

• I Международной заочной научно-технической конференции «Алгоритмические и программные средства в информационных технологиях, радиоэлектронике и телекоммуникациях» (Тольятти, 2013 г.).

Публикации

Основные результаты диссертации опубликованы в 11 работах, 5 из которых опубликованы в изданиях, рекомендованных ВАК, и приравненных к ним. Личный вклад автора

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

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

Общий объём диссертации - 150 страниц. Диссертация состоит из введения, 9 основных разделов, заключения, списка используемой литературы из 83 наименований, а также предметного указателя и приложений.

2. КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ ВВЕДЕНИЕ

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

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

я-подклассы15 нужно рассматривать в контексте т.н. последовательностных (sequential16) языков. Контекстно-свободная грамматика с множеством правил Р называется последовательностной, если на множестве её нетерминалов можно определить такой линейный порядок, что ни одно из правил не содержит в правой части ни один из «предыдущих» нетерминалов. Контекстно-свободный язык называется последователыюстным, если он порождается хотя бы одной последовательностной грамматикой.

Для определения л-подклассов наряду с целыми неотрицательными числами (множество N) рассмотрим эти же числа со штрихом, обозначая N' = {О', Г, 2', 3',... } и используя для элементов N'kjN следующее естественное соглашение

0<0'< 1 < 1'<2<2'< ... При этом е -правило из множества правил Р будем называть правилом порядка 0. Правило А—*а при а&е называется правилом порядка 0', если правая часть этого правила не содержит А.

Правило А—>а последовательностной грамматики называется правилом порядка к (к е. N), если правая часть этого правила содержит А к раз, причём в записи сх = р0л(1)р1л(2)...р*_1л(*)р* либо р0=е,либо Р4=е.

Правило А->а последовательностной грамматики называется правилом порядка к' (к' е N'), если правая часть этого правила содержит А к раз, причём в записи a = P0/l(1)P1^(2)..Pil_1/l(i)PJt должно быть ро*е,либо р*

Порядком последовательностной грамматики называется наибольший порядок её правил. Порядком последовательностного языка называется наименьший из порядков порождающих этот язык грамматик. Для / е iV u N' множество последовательностных языков, имеющих порядок, не превышающий г, будем обозначать 7t(/). Объединение всех л(г) будем обозначать 7t(co). При этом:

15 Это описание является авторской модификацией описания, приведённого в статье: Мельников Б. Об одной классификации последовательностных контекстно-свободных языков и грамматик // Вестник Моск.ун-та, сер. Вычисл. матем. и киб-ка. 1993. № 3. С. 64-69.

16 Samir Е. On sequential languages // Z. Phonetik, Sprach. Kommunikationsforsch. 1965. 18. P. 61-69.

• 7Г(0) состоит из языков О и { Б};

• 7Г(0') есть множество конечных языков;

• 71(оо) представляет собой множество последовательностных языков;

• и, наконец, 71(1) есть множество регулярных языков.

Недетерминированные конечные автоматы (НКА) представляют собой пятерку К={(У, 2, 8, £ Р}, где:

• б - некоторое конечное множество состояний (вершин);

• £ - рассматриваемый алфавит;

• 5 - функция переходов вида 5 : 0 х I Р(0), где Р(® - множество всех подмножеств 0;

• $£<2-множество стартовых состояний (входов);

• РЯ 6 - множество финальных состояний (выходов).

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

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

Рисунок 1 - Пример конечного автомата для языка, задаваемого РВ (а + аЬ + Ьа)\

Как и в случае с регулярными выражениями один и тот же регулярный язык может задавать бесконечное число НКА. Встаёт вопрос о поиске автоматов-инвариантов для заданного языка. Такими автоматами являются канонический (минимальныи детерминированный автомат), базисный и универсальный Кроме того, можно установить сюръективное отношение между множеством регулярных языков и множеством всех таблиц бинарного отношения #.

РАЗДЕЛ 1. Применяемый подход к исследованию регулярных языков

Для некоторого регулярного языка I и некоторого конечного автомата К={<2 I 5, /р, задающего этот язык, а также для канонического автомата I £,'§ ' ^ Гц/ этого языка определим прямую функцию разметки

следующим образом. Для любого де д и д<1 е <£ ^(д) содержит в том и только том случае, если

'-1 (Я) П 4" Г<7о/ .

При этом положим ф" (д)=

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

Далее рассмотрим специальное бинарное отношение # на множестве (¿х % О. — множество состояний канонического автомата, а <¡1 - и множество состояний канонического к зеркальному. Для каждой пары А е (¿и X в ^.положим А # Хв том и только том случае, когда

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

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

В качестве примера рассмотрим данное отношение для языка, задаваемого регулярным выражением (а + аЬ + Ьа)* (автомат приведён на рисунке 1). Эквивалентный ему канонический автомат изображён на рисунке 2, а. Язык в данном случае совпадает с инверсным, поэтому канонический автомат к инверсному языку совпадает с каноническим автоматом заданного языка.

Ь) канонический автомат языка, инверсного к нему. Таблица 1 - Таблица отношения # для языка, задаваемого РВ (а + аЬ + ha) .

x y z

a # #

в # # #

с #

На основе этих автоматов, согласно определению бинарного отношения #, получаем таблицу 1.

Будем говорить, что пара подмножеств Q с Q.H Re: образует псевдоблок, если для любых А е Qh x е ^.выполняется А IIx. Если, кроме того, любая пара

"См. сноску 12.

18 Melnikov В. Once more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae. 2010. Vol. 104, No. 3. P. 267-283.

" Melnikov B. A new algorithm of constructing the basis finite automaton // Informatika (Lithuanian Acad. Sci. Ed.). 2002. 13 (3). P. 299-310.

множеств ' и Лтаких что б с £> с Ои Я с Л 'с образует псевдоблок тогда и только тогда, коща {?'={? и Я' = Д, то будем говорить, что пара 0 и Л образует блок.

Обозначим псевдоблок записью В((), К). Для такого псевдоблока В через а(В) обозначим соответствующие ему состояния е а через (3(5) - соответствующие состояния йс^

Для приведённого выше примера выпишем псевдоблоки: {А, В} X {*}; {В} х {X, Г, г); {А, С] х {У}; {В} х {У, г};

{В, С) х {У}; {Л,Я}х{У}; {Л}х{*}; {С}Х{У};

и5} X {X, Г); {А) X {У}; {В} х {л; г}; {5} х {X, У};

И, Я, С} X {У}; {А} х {X, У}; {В} х {У}; {В} х {*}

{В} х {г}. Выберем из них блоки

ЬХ = {А,В) х {Х,П; Ь2={В} х {ДУ,2}; Ь} = {А,В, С} х {У}. (1) Состоянию любого конкретного автомата для данного языка соответствует некоторый псевдоблок. Более того, очевидным необходимым условием для определения данного языка конечным автоматом является то, что подмножество псевдоблоков, соответствующих множеству состояний рассматриваемого автомата, покрывает все элементы отношения #.

РАЗДЕЛ 2. Автомат СОМ

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

Положим Фгеб^Ф/, а) при одновременном выполнении следующих двух условий:

для любого деа(Ф1) выполняется 8^(9, а) с а(<8г), для любого де р(«г) выполняется а) с Р(ФД (2)

где боиб*- функции переходов канонических автоматов, задающих языки I и £ соответственно. Отметим, что в приведенном определении мы специально не допускаем возможности а = е.

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

Для того чтобы состояние дед могло быть входным, необходимо выполнение условия з^е <р'" (д), где (единственное) входное состояние канонического автомата.

Для того чтобы состояние <760 могло быть выходным, необходимо выполнение условия {д), где - (единственное) входное состояние канонического автомата для языка Iй

Используя последние утверждения, опишем множества стартовых и финальных состояний автомата СОМ. Положим «,е 5®, если одновременно выпол-

пяются следующие условия:

• существует такое q¡&a (®i), что q¡e 5<¿;

• существует такое q2e Р ((В,), что q2e F<¡>, (2') где 5<¿h /4- множество стартовых состояний канонического автомата к данному и множество финальных состояний канонического к инверсному соответственно.

Положим <Bi е F®, если выполняются оба условия:

• существует такое q¡ea (%), что q,e F(¿

• существует такое q2e р (в,), что q2e 5*, (2") rae Fq и 5л - множество финальных состояний канонического автомата к данному и множество стартовых состояний канонического к инверсному соответственно. Объединив все вышеперечисленное, определим автомат СОМ. Автоматом СОМ к заданному языку L называется пятёрка

СОМ (!)={«, I, 5„, Sv, F*}, rae:

• <В - множество всех блоков для L;

• I - алфавит;

• 5« - функция перехода, определённая выше;

• 5а с Ф множество стартовых состояний;

• Fqc: <В множество финальных состояний.

Отметим, что это определение даёт алгоритм построения автомата СОМ.

а) Ь)

Рисунок 3 - а) Автомат СОМ без входов и выходов; Ь) автомат С<Ш языка (а + аЪ + Ьа) .

В качестве примера продолжим рассмотрение рмулярного языка (а + аЬ + Ьа)* или, что то же самое, автомата, приведённого на рисунке 1. Мы уже получили блоки бинарного отношения # для этого языка (1). Таким образом, мы получили множество состояний автомата СОМ. Воспользуемся определением функции переходов 6®, чтобы построить дуги автомата СОМ Согласно приведённым ранее определениям, для того чтобы в автомате СОМ существовала дуга с пометкой а из блока, к примеру, Ьх в блок Ь2 необходимо, чтобы хоть одно состояние из а(6|) (т.е. из состояний А, В) канонического автомата имело переход с пометкой а в какое-нибудь состояние из а(Ь2) (т.е. в состояние В), при этом также необходимо, чтобы в каноническом автомате к инверсному языку имелась дуга с пометкой а из одного из состояний Р(62) (т.е. X. 4,7) в какое-нибудь состояние из (3(^1) (т.е. X, У). В нашем случае дуга г>, будет существовать в

автомате СОМ. Проведя такие действия необходимое количество раз. получим автомат без входов и выходов (рисунок 3, а).

Согласно определениям входов и выходов для автомата СОМ, блок Ь является стартовым/финальным, если а(Ь) содержит стартовое/финальное состояние канонического автомата, а р(6) - финальное/стартовое состояние канонического автомата к инверсному языку.

Автомат СОМ для языка (а+ аЬ+ Ъа) приведён на рисунке 3, Ь.

РАЗДЕЛ 3. Универсальный автомат Конвея

Универсальный автомат имеет несколько определений20. Приведём одно из них.

Псевдофакторизацией заданного регулярного языка Ь называется такая пара языков (X; У) над алфавитом Е, что для языка ХУ = {гп | и е X, V е 1'} выполнено условие ХУ с!,

Факторизацией регулярного языка I называется его максимальная псецдо-факторизация (X, У), т.е. если X с X', У с У и А'Т' с I, то X = X' и У = У'

Обозначим множество всех факгоризаций языка Ь как Т^

В факторизации (X, У) язык X называется левым фактором, а Г - правым фактором. Так как е = ¿ е = I, является одновременно и левым и правым фактором, которому соответствуют правый фактор Ус и левый фактор Хг Будем называть (Х£, Ь) стартовой факторизацией, а (Кс, Ь) — финальной факторизацией.

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

Универсальным автоматом иь для заданного регулярного языка Ь называется пятёрка

где:

. 81 :хБ Р(Г£) и (Х\Г) б 6г {(х.Па), если ХаУ с Ь ■ = {(Х,У)еТ£\геХ}-

Отметим, что данное определение не является конструктивным, т.е. оно не даёт алгоритма построения универсального автомата. Для получения такого алгоритма нужны дополнительные построения.

Утверждение. Универсальный автомат 1!ь задаёт язык Ь.21

РАЗДЕЛ 4. Совпадение автоматов СОМи универсального

В этом разделе рассмотрено понятие подавтомата и определены вспомогательные объекты, необходимые для доказательства совпадения автоматов СОМ и универсального автомата. Также в разделе приведено доказательство справедливости утверждения об этом совпадении.

Согласно определению, приведённому Лаллеманом22, автомат

См- сноску 11, или: Lombardy S., Sakarovitch J. The Universal Automaton // Logic and Automata, Texts in Logic and Gaines. Amsterdam: Univ. Press. 2008. Vol. 2. P. 457-504. См. там же.

£' = {(?', ЦЗ'.^'.Г') называется подавтоматом автомата К, если выполняются условия:

• 8'(9,<з)сб(д,а) длялюбых и ае I.

Очевидно, что подавтомат определяет язык-подмножество, который в некоторых случаях совпадает с исходным языком. 1

Утверждение. Всякий задающий язык Ь минимальный (недетерминированный) автомат является подавтоматом универсального автомата, определяющего этот язык.23

Для доказательства равенства универсального автомата и автомата СОМ были даны другие связанные определения.

Будем называть автомат К* ={2*Д,5*,5*,/Г"} псевдоподавтоматом автомата К, если он для некоторой функции к £>*—*• б удовлетворяет следующим условиям:

• любому состоянию д автомата К соответствует некоторое состояние д-И(д ) автомата К;

• для каждой пары состояний и д2' автомата А'* условие д2 выполняется тогда и только тогда, когда для автомата К и его состояний Ыд\) и Ыд'2) выполняется Цд'2) .

Для любых о е I, д'\^'2 дуга д'—соответствует дуге /г(д') >Ыд'2), если выполняются условия д'2 б 5*{д\,а) и к{д'2) еЪ{И{д\),а). Очевидно выполнение следующих утверждений.

) с Г-тд,)) и 1°»!{д'г) С ЬТ(к{д2)).

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

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

Пусть для заданного регулярного языка Ь построены универсальный автомат и автомат СОМ

Теорема. = СОМ(П) (с точностью до переобозначения состояний). Доказательство. Универсальный автомат задаёт язык ¿, и всякий автомат, определяющий этот язык (в том числе и СОМ(Ь)), является подавтоматом универсального24. Автомат СОМ(Ь). кроме того, является его наполненным псеадо-подавтоматом, что следует из определений, приведённых выше.

~ Лаллеман Ж. Полугруппы и комбинаторные приложения. М.: Мир, 1985.440 с. (гл. 6, п. 1).

23 См. сноску 9.

24 См. сноску 9.

Автомат COM - инвариант языка, см. [2]. Любой автомат для заданного языка является подавтоматом и псевдоподавтоматом СОМ'а25. В частности, универсальный автомат является подавтоматом и наполненным псевдоподавтома-тох, что следует из определения факторизации.

Итак, автомат СОМ является наполненным псевдоподавтоматом универ-салшого, а универсальный автомат, в свою очередь, является наполненным псевдоподавтоматом автомата. СОМ. Следовательно, согласно приведённому выше определению наполненного псевдоподавтомата, они совпадают.

РАЗДЕЛ 5. Применение универсального автомата -практические алгоритмы

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

Другим возможным подходом может стать построение минимального автомата на подмножестве множества блоков заданного языка, причём такое подмножество должно быть покрывающим26. Т.е. задача минимизации в этом случае сводится к более общей задаче построения автомата на основе подмножества блоков. В диссертации предлагается 2 эквивалентных алгоритма построения такого автомата - приведём их краткое описание.

Алгоритм 1 (построение «снизу вверх»):

Вход: Подмножество множества блоков П, канонические автоматы L и i". Выход: Конечный автомат (подавтомат универсального), соответствующий подмножеству Q.

Шаг 1: Строим блоки и соответствующие им вершины.

Шаг 2: Строим дуги по принципу построения дуг в автомате СОМ (согласно (2)). Шаг 3: Определяем входные и выходные состояния (согласно (2') и (2")).

Алгоритм 2 (построение «сверху вниз»):

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

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

Несмотря на схожесть описания, практические реализации этих алгорит-

25 Melnikov В., Sciarini-Guryanova N. Possible edges of a finite automaton defining a given regular language // The Korean J. Comp, and Appl. Math. 2002. Vol. 9, No.2. P. 475-485.

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

мов принципиально различны.

Теорема: описанные алгоритмы эквивалентны, т.е. построенные на основе этих алгоритмов автоматы совпадают.

Справедливость этой теоремы следует из определения автомата СОМ.

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

РАЗДЕЛ 6. Возможная неэквивалентность исходного и покрывающего автоматов

В 6-м разделе рассматривается проблема неэквивалентности покрывающего автомата и исходного. В процессе построения минимального автомата мы определённым образом (индивидуально для каждого типа минимизации) выбираем блоки из таблицы бинарного отношения #, чтобы получилось покрывающее множество28. Однако покрывающий автомат - автомат, построенный на покрывающем подмножестве блоков в соответствии с одним из алгоритмов из раздела 5 — в некоторых случаях может оказаться неэквивалентным исходному. Такая проблема характерна, например, для т.н. автомата Waterloo29 и некоторых дру-ных30.

Таблица 2 - Таблица отношения # и блоки для неё.

• (1) {А, В} х {X, Y}

■ (2) {В, С} х {Y, Z}

■ (3) {А, В, С} х {Y}

• (4){BI х{Х, Y,Z}

X Y Z

А # и

В # и и

С и #

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

Итак, при помоши специального программного обеспечения31 было сгене-

27 Подробнее об этом см. в разделе 6.

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

29 См. сноску 10.

30 Polák L. Minírnalizations of NFA using the universal automaton // Int. J. Found. Comput. Sei. 2005. 16 (5). P. 999-1010.

"1 Краткое описание разработанного автором диссертации программного обеспечения см. ниже (раз-

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

РАЗДЕЛ 7. Подход к описанию контекстно-свободных языков с помощью расширения универсального автомата

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

Для каждого п из множества Л^, рассмотрим множества

ЛГ<„)={ 1,2, ...,«-1, п) и г(п)={-п,~(п-1), ...,-2,-1,0, 1,2, ...,п-\,п}. (Каждый элемент 1 из множества А\п) символизирует ¿-ю пару скобок. Также /' символизирует ;'-ю открывающую скобку, а -/ - соответствующую закрывающую скобку.)

Для заданного п > 0 будем называть [2(я)*] языком, согласованным по скобкам (а каждое его слово - словом, согласованным по скобкам).

Рекурсивно определим слово, согласованное по скобкам:

• е и 0 — согласованные по скобкам слова;

• если м> и V - согласованные слова, то и=™ - тоже согласованное по скобкам слово;

• если та/ - согласованное слово, г 6 Щп), то и=;и'-г - тоже согласованное по скобкам слово;

• никакое другое слово не является согласованным по скобкам.

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

Определим скобочный автомат В следующим образом:

¿ИеДл,^,«), (3)

где п ИЗ N0 определяет множество скобок 7Г„), X - функция переходов вида Х;2х е_Р((1и{е})х7(„)).

Далее определим язык автомата (3) - будем обозначать его записью ЦБ).

Пусть для последовательности <70, <7ь ■ ■•• <?*, состояний из <2 выполняются следующие условия:

• Ча е дт е р,

• (я*, 4) 6 X Як+1) для каждого к из множества {0.....т-1};

• '1 Н — I», е [2м*].

Тогда мы считаем, что слово а, а2 ... ат принадлежит Ь(В). Никаких иных

дел 9).

слов язык Ь(В) не содержит.

Скобочные автоматы В\ и В2 называются эквивалентными, если - ЦВ\) = ЦВ2).

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

Теорема I. Язык, распознаваемый автоматом (3), является контекстно-свободным.

Справедливо и обратное утверждение.

К автомату В, как и к классическим НКА, применяются различные алгоритмы эквивалентного преобразования (построение минимальных автоматов, универсального автомата и пр.).

Теорема 2. Пусть К] и К2 - некоторые недетерминированные конечные автоматы над алфавитом Ч7, причем ЦК,)=ЦК2). Тогда ЦВ(К.\))=ЦВ(Кг)).

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

Для этого введено понятие скобочных и правильных скобочных автоматов. Понятие правильных скобочных автоматов основано на том, что слова языка, определяемого этим автоматом согласованны по скобкам. При применении алгоритмов эквивалентных преобразований обычных НКА к скобочным автоматам последние сохраняют свою правильность.

РАЗДЕЛ 8. Применение универсальных автоматов

для моделирования некоторых процессов микроэкономики

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

Рассматриваемая модель управления организацией зависит от критериев долгосрочной оптимальности, в число которых входят не только количественные. но и качественные показатели, связанные с нуждами организации и учитывающие неопределённость исходной ситуации32. Модель предполагает т.н. многофокусность управленческого действия, а также учитывает не только результаты, но и характеристики процесса достижения цели. Для последнего вводится понятие «ценностного ориентира» как основной характеристики организации, влияющей на скорость организационных и управленческих изменений в предприятии. Такая характеристика должна быть оптимальной по заданному набору критериев. Каждая организация формирует собственный набор ценностных ориентиров, которыми она будет руководствоваться при совершении т.н. управленческих воздействий (УВ)33. Процессы совершения УВ могут быть алгоритмизированы.

3~ Дилигенский Н.В., Дымова Л.Г., Севастьянов П В. Нечеткое моделирование и многокритериальная оптимизация производственных систем в условиях неопределенности: технология, экономика, экология. М.: «Издательство Машиностроение — 1», 2004. 8 с.

33 См. там же.

Был описан набор таких алгоритмов34, реализованных с использованием аппарата сетей Петри. В описанном подходе моделирования УВ встаёт проблема минимизации числа состояний и (или) переходов в сети Петри, в решении которой может помочь аппарат теории недетерминированных конечных автоматов (НКА).

Для этого предлагается алгоритм оптимизации сетевой модели, который предполагает три этапа: сведение сети Петри к недетерминированному конечному автомату; оптимизация НКА; сведение оптимизированного НКА к новой сети Петри (модифицированной и имеющей, вообще говоря, меньшее число событий - но являющейся эквивалентной исходной).35

РАЗДЕЛ 9. Программный комплекс

В этом разделе приводится описание написанного в рамках работы над диссертацией программного комплекса. Он был реализован на языке Java36 с использованием парадигмы ООП. Некоторые модули были дополнительно написаны в системе GAP37. Программы не имеют пользовательского интерфейса и работают через консоль.

Они предназначаются для практического исследования закономерностей появления проблемы неэквивалентности покрывающего автомата и исходного. Помимо этого в комплексе был реализован алгоритм построения автомата СОМ. Комплекс состоит из 5 модулей:

• модуль чтения из XML;

• модуль, реализующий логику работы автомата:

о построение зеркального автомата, о построение канонического автомата,

о построение универсального автомата и покрывающего автомага на основе покрывающего множества блоков;

• модуль построения автомата из покрывающего множества блоков путём удаления состояний из универсального автомата;

• модуль построения таблицы отношения #;

• модуль нахождения блоков;

• модуль нахождения всех возможных сочетаний блоков.

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

34 Зубова Т.Н., Мельников Б.Ф. Использование сетей Петри для моделирования процесса принятия управленческих решений// Вектор натай ТГУ 2011. № 3(17). С. 33-37.

35 Подробное описание примера моделирования УВ с помощью сети Петри и последующую оптимизацию модели можно найти в: Зубова Т.Н. Некоторые вопросы математического моделирования управления организацией с учетом долгосрочной оптимальности: дис. ... канд. физ.-мат. наук: 05.13.18, Тольяттинский государственный университет, Д212.264.03, защищена 13.04.2012 / Т.Н. Зубова - Тольятти: ТГУ, 2012. - 155 с. См. также [10].

36 J2SE 6.0 (jdkl.6.0_20)

37 http://www.gap-system.org/ - официальный сайт системы GAP.

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

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

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

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЯ

В приложениях приведены тексты программного комплекса с достаточными для понимания текстов комментариями.

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

• Исследованы основные свойства автомата СОМ, вытекающие из его определения.

• Доказано равенство автомата СОМ и универсального.

• Описаны алгоритмы решения некоторых задач теории формальных языков на основе универсального автомата.

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

• На основе универсального автомата описаны алгоритмы решения некоторых прикладных задач теории формальных языков (в первую очередь - вспомога-

38 Мельников Б.Ф., Пивнева C.B., Рогова O.A. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов // «Стохастическая оптимизация в информатике». С.-Пб: Изд-во С.-Петербургского университета, 2010. Т. 6. С. 74 - 82. См. также: Рогова O.A. Подход к оценке репрезентативности случайно сгенерированных дискретных структур на примере недетерминированных конечных автоматов: дис. ... канд. физ.-мат. наук: 05.13.18, Тольяттинский государственный университет, Д212.264.03, защищена 13.04.2012 / O.A. Рогова - Тольятти: ТГУ, 2012. - 115 с.

тельные алгоритмы для задач минимизации недетерминированных конечных автоматов).

• Описаны алгоритмы практического применения автомата СОУЛ и его расширенных вариантов: для описания подклассов класса КС-языков и для математического моделирования некоторых задач микроэкономики.

• Описан программный комплекс, включающий реализацию рассматриваемых в диссертации прикладных задач.

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

4. ПУБЛИКАЦИИ АВТОРА

Публикации в изданиях, рекомендованных списком ВАК,

и приравненные к ним:

1. Мельников Б.Ф., Зубова М.А. Построение автомата СОМ на основе базисного автомата // Вектор науки Тольяттинского государственного университета. 2010. №4 (14). С. 30-32.

2. Мельников Б.Ф., Зубова М.А. Об одном алгоритме построения универсального автомата Конвея // Вестник Воронежского государственного университета. 2012. № 1.С. 135-137.

3. Долгов В.Н., Зубова М.А. Доказательства совпадения автоматов СОМ и универсального // Вектор науки Тольяттинского государственного университета. 2012. № 1 (19). С. 25-28.

4. Зубова М.А. Об одном подходе к моделированию контекстно-свободных грамматик недетерминированными конечными автоматами // Вектор науки

' Тольяттинского государственного университета. 2012. № 4 (22). С. 49-55.

5. Вылиток A.A., Зубова М.А., Мельников Б.Ф. Об одном расширении класса конечных автоматов для задания контекстно-свободных языков // Вестник Московского университета, серия 15 («Вычислительная математика и кибернетика»), 2013. № 1. С.39-45.

Публикации в рецензируемых научных журналах и изданиях:

6. Зубова М.А., Мельников Б.Ф. Об одном алгоритме построения универсального автомата Конвея // сб. науч. тр. Всероссийского конкурса научно-исследовательских работ студентов и аспирантов в области информатики и информационных технологий в рамках Всероссийского фестиваля науки в НИУ БелГУ. 2011. Т. 2. С. 419-423.

7. Зубова М.А., Крайнюков Н.И., Мельников Б.Ф. Бидетерминированные конечные автоматы и универсальный автомат Конвея // статья в коллективной монографии «Эвристические алгоритмы и распределённые вычисления в прикладных задачах». Тольятти: Изд-во ТГУ, 2012. С. 99-114.

8. Долгов В.Н., Зубова М.А. Распределённый алгоритм построения универсального автомата Конвея // статья в коллективной монографии «Эвристи-

ческие алгоритмы и распределённые вычисления в прикладных задачах». Тольятти: Изд-во ТГУ, 2012. С. 90-98. 9. Зубова М.А. Применение конечных автоматов для моделирования распознавателей, определяющих контекстно-свободные языки И статья в коллективной монографии «Эвристические алгоритмы и распределённые вычисления в прикладных задачах» (выпуск 2). Тольятти: Изд-во ТГУ, 2013. С. 36-47. Ю.Зубова М.А. Подход к моделированию автомата с наличием проблемы неэквивалентности покрывающего автомата. // Исследования в области естественных наук. - Март, 2013 [Электронный ресурс]. URL: http://science.snauka.ru/2013/03/4482 П.Зубова М.А.. Зубова Т.Н. Об одном подходе к оптимизации модели оптимального направления движения организации // I Международная заочная научно-практическая конференция «Научная дискуссия: вопросы математики, физики, химии, биологии». М.: Изд. «Международный центр науки и образования», 2013. С. 37-43.

Подписано к печати 16.05.2013г. Формат 60x84/16. Бумага офсетная. Гарнитура ТИК. Печать оперативная. Тираж 100 экз., заказ № 1143

Отпечатано в типографии Ника. Лицензия на полиграфическую деятельность №004812968 от 19.09.2008г.