Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Аннотация

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



Abstract

In the paper, the applied software for the interactive solution of exercises in the field of discipline “Theory of automata and grammars” is implemented. The aim is to simplify the mastering of the specified field by complementing traditional teaching methods with a modern computer-assisted approach. It is supposed to provide various possibilities, such as the interactive demonstration of classical algorithms, local environment for remote practice and quick access to reference materials. In this work, analogues of the proposed software system have been analyzed, the methods of programmatic implementation of typical algorithms of the “Theory of automata and grammars” have been chosen, a diagrammatic representation of the system has been created and a prototype with a sufficient basic functionality has been designed. Finally, several manuals have been written as a basis for future research and modifications.



Введение

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

В то же время, начинающие специалисты в процессе получения образования регулярно сталкиваются с такими проблемами, как неточность объяснений, недостаточность практики, отсутствие индивидуального подхода, несовершенство традиционных методов разбора задач. Неэффективно расходуется личное и академическое время преподавателей и студентов. Как следствие, в структуре полученных знаний остаются «пробелы», у студентов отсутствует общая картина понимания текущих и предстоящих профессиональных потребностей, страдает общее качество образования. Из этого вытекает неспособность выпускников, в том числе, российских, соответствовать требуемому уровню компетентности [2].

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

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

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

Теория автоматов и формальных грамматик часто оказывается включённой фрагментарно в другие технические дисциплины. К примеру, в МИЭМ НИУ ВШЭ на образовательной программе элементы данной области знаний изучались студентами в рамках курсов «Лингвистическое и программное обеспечение автоматизированных систем» и «Теория автоматов и управление» [5]. Обе дисциплины имели выраженный практический уклон: студентам предлагалось выполнять домашние задания и лабораторные работы, при своевременной и качественной сдаче которых освоение теоретических вопросов не проверялось. И, хотя данное решение имеет положительные стороны, у многих студентов не сформировалось целостное понимание прикладного применения полученных навыков. Кроме того, если задания по первой дисциплине выполнялись в электронном виде, то по второй решались, как правило, на доске или бумаге. Нельзя сказать, что это в корне неверный подход, однако, наблюдались растрата времени, неаккуратность работ и сопутствующие трудности в проверке, оставшиеся неясности; кроме того, студенты демонстрировали больший интерес к первой (компьютеризованной) дисциплине, что можно объяснить возможностью ощутить большую вовлеченность в процесс. Данные проблемы можно считать свойственными и другим учебным заведениям.

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

Таблица 1. Проблемы теории автоматов и грамматик

Проблема	Решение
Со стороны преподавателя
Затраты времени на составление заданий	Каталог и конструктор классических задач, параметризация существующих примеров
Затраты времени преподавателя на проверку работ учащихся	Автоматизированная проверка
Необходимость транспортировки большого количества бумажных отчётов; затруднение при проверке рукописного текста	Электронная форма отчёта
Несбалансированность теории и практики в рамках традиционного преподавания	Наличие в системы необходимых материалов как теории, так и практики; поощрение освоения, контрольные вопросы
Отсутствие понимания студентами возможностей прикладного применения приобретённых навыков	Каталог творческих заданий, возможность дополнения его преподавателем, практические примеры
Трудности планирования учебного процесса в условиях множественности учебных групп, бригад, потоков	Автоматизированное планирование, электронное расписание
Со стороны студента
Затраты времени при решении задач на бумаге	Решение задач в электронной форме
Обратно пропорциональная зависимость между временем, затраченным на оформление задания, и аккуратностью; предпочтение преподавателем аккуратных работ, риск необъективной оценки непосредственного задания	Автоматизированное оформление отчёта в электронном виде
Нехватка индивидуального подхода, времени на решение возникающих вопросов, консультаций; затраты времени на самостоятельный поиск либо нагрузка преподавателя во внеучебное время	Релевантная справочная система по текущей теме, интерактивные образцы решения
Необходимость личной сдачи бумажной работы даже при отсутствии требования очной защиты	Отправка выполненного задания преподавателю напрямую с компьютера студента
Потеря ориентации студента в учебном процессе вследствие пропуска темы	Доступность пройдённых тем, отметка прогресса, автоматические напоминания, связь с преподавателем
Зависимость от присутствия преподавателя и его компетентности	Программная система - третья сторона в образовательном процессе

Краткий анализ существующих технических и инструментальных средств, направленных на решение означенных проблем, показывает, что, хотя к настоящему моменту ряд разработок уже сделан, они имеют некоторые недостатки. Во-первых, немногие из них могут предложить комплексность подхода. Практически каждая из существующих программ предназначена для выполнения узкой задачи, и даже при условии того, что она качественно справляется с этой работой, для применения в образовании подобная программа будет неэффективна. Во-вторых, узконаправленные инструменты, реализованные в различном виде (локальное приложение, веб-приложение) потребуют от студента или преподавателя постоянной смены фокуса, что также является нежелательной чертой. В-третьих, некоторые имеют неудобный интерфейс. В-четвертых, многие программы являются иноязычными, и, хотя для специалиста в сфере информационных технологий давно требуется знание иностранного языка, на этапе обучения эта особенность может отрицательно влиять на способность воспринимать критическую информацию. Так, наиболее приблизившаяся к заявленной цели система JFLAP [6], разрабатываемая в университете Дьюка (США) с 1997 года, написана на английском языке, а также направлена, в первую очередь, на демонстрацию, а не на самостоятельное освоение.

Цель и задачи

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

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

· построение детерминированных конечных автоматов (ДКА) по конечному автомату (КА);

· работа с диаграммами или таблицами переходов, задающими КА;

· построение КА, допускающих язык, порождаемый грамматикой с определёнными правилами;

· построение КА, допускающих цепочки из {0,1}* и определёнными условиями;

· работа с регулярными грамматиками для языка, заданного выражением, КА или грамматикой с правилами;

· построение КС-грамматики для языка;

· строить автомат с магазинной памятью (МП) по контекстно-свободной (КС) грамматике с правилами;

· строить детерминированный МП-автомат для языка.

Для удобства пользователя программа должна уметь следующее:

· позволять пользователю интерактивно вводить параметры задачи;

· показывать допустимость выводимых цепочек в виде последовательности конфигураций автомата.

Для достижения цели потребуется решить следующие задачи:

· Задачи теоретической подготовки:

o исследовать существующие разработки в данной области, обладающие требуемым или схожим функционалом, учесть сильные и слабые стороны, выделить особенности реализации и установить технические ожидания от собственной ПС;

o ознакомиться с объектами предметной области ;

· Задачи формализации ПС:

o привести алгоритмы решения выбранных задач в алгоритмическом виде;

o сформировать требования к способам взаимодействия пользователя с ПС;

o спроектировать ПС с применением унифицированного языка моделирования (UML);;

· Задачи программирования:

o разработать прототип ПС на языке высокого уровня;

o разработать пользовательский интерфейс ПС;

o провести тестирование и отладку, добиться стабильного состояния;

· Задачи подготовки рекомендаций:

o составить общее описание системы;

o составить инструкцию по модификации протитипа;

o составить инструкцию по использованию прототипа.

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

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

Во второй главе произведена формализация алгоритмов и приведено описание общей модели на унифицированном языке моделирования (UML).

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



1. Обзор предметной области

интерфейс грамматика алгоритм файл

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

1.1 Теоретические основы теории автоматов и грамматик

Будут рассмотрены исследуемые области научного знания и приведена их взаимосвязь. Сведения, изложенные здесь, опираются на сведения из распространяемых учебных пособий [7, 8].

1.1.1 Ключевые понятия

Теория автоматов (ТА) - область научного знания, изучающая абстрактные вычислительные устройства («автоматы»). Область плотно связана с теорией алгоритмов и математической логикой. Теория формальных грамматик (ТФГ) - область, изучающая способы описания некоторых формальных языков посредством задания набора правил языка.

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

Основными понятиями в теории автоматов и грамматик являются:

Алфавит (?). Конечное непустое множество допустимых символов. Понятие степени алфавита (?k) характеризует множество всех цепочек длины k, которое можно составить из алфавита ?.

Цепочка/слово. Последовательность символов алфавита. Может быть пустой (е). Применяются понятия длины цепочки (например, для цепочки w длина обозначается как |w|), множества цепочек над алфавитом (?*) или непустых цепочек над алфавитом (?+).

Язык/формальный язык (L). L - язык над алфавитом, если L ? ?*. Может быть описан грамматикой, регулярным выражением, конечным автоматом, БНФ-конструкцией или простым перечислением слов.

Грамматика (G). Определяется так:

G = <N, T, P, S>

Где N - множество нетерминалов,

T - множество терминалов,

P - множество правил подстановки (продукций),

S - стартовый символ.

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

Терминал. Символы, из которых состоят цепочки языка. Принято обозначение строчными символами.

Продукция. Правило вывода, представляющая рекурсивное определение языка. Состоит из головы, символа продукции (>) и тела. Голова и тело - цепочки символов над алфавитом N ? T, причём голова должна включать хотя бы один нетерминал, а тело может быть пустым (е).

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

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

Контекстно-зависимые (КЗ). Правила имеют вид бAв > бгв (нетерминал в левой части может быть заменён при наличии контекста).

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

Регулярные (А). Правила вида A > гB, A > B или A > е (праволинейная грамматика). Новые цепочки порождаются добавлением последовательности справа (слева для леволинейной).

Данные типы грамматик связаны с автоматами различного типа и могут быть преобразованы в них (рис. 1).

Рисунок 1. Связи между грамматиками и автоматами

Форма Бэкуса-Наура (БНФ). Система описания синтаксиса КС-грамматик, в которой одни нетерминалы последовательно определяются другими в стандартизированной форме. Расширенная БНФ (РБНФ) является доработанной формой данной системы с более ёмкими правилами. В общем виде, правило составляется в виде:

идентификатор = выражение.

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

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

1. Оператор «звёздочка», или замыкание Клини. Обозначается как L*. Результат операции - множество цепочек любой длины, образованных путём соединения любых последовательностей из L. Применяется к наименьшему правильно построенному регулярному выражению слева от оператора «*».

2. Оператор «точка», или конкатенация. Ассоциативный. Результат работы - последовательная запись указанных цепочек.

3. Оператор объединения. Ассоциативный. Результат работы - множество цепочек из двух языков без повторений.

Для работы с грамматиками, в частности, при построении компиляторов, применяются лексические и синтаксические анализаторы. Лексический анализатор определяет роли использованных токенов (лексем) в процессе разбора входной цепочки на распознанные группы. Известные примеры: lex, flex. Синтаксический анализатор (парсер) преобразует последовательность распознанных токенов в структурированный формат (дерево), отражающий иерархию исходного текста. Выделяют LL (нисходящие) и LR (восходящие) парсеры. Примеры: Yacc, Bison, COCO/R, Ragel и др.

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

Формальное представление. Имеет следующий вид:

A = (Q, ?, д, q0, F)

Где A - имя автомата,

Q - множество состояний,

? - множество входных символов,

д - функция переходов,

q0 - начальное состояние,

F - множество заключительных (допускающих) состояний, F ? Q.

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

Рисунок 2. Пример диаграммы переходов ДКА.

Таблица переходов. Представление, при котором строки соответствуют состояниям (q), столбцы - входным символам (a), а на пересечении находится значение функции переходов д(q, a). Стрелка (>) отмечает начальное состояние, звёздочка (*) - конечное. Пример на рис. 3.

Рисунок 3. Пример таблицы переходов ДКА

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

Автомат с магазинной памятью (МП-автомат) имеет особую структуру (стек) под названием магазин, куда могут быть помещены (или извлечены) символы в ходе работы автомата. Формальное определение сходно с определением простого КА, однако, имеет отличия:

P = (Q, ?, Г, д, q0, Z0, F)

Где Г - конечный магазинный автомат (множество символов, допустимых для помещения в магазин),

Z0 - начальный магазинный символ («маркер дна»).

Функция переходов д, в отличие от простого КА, выглядит как д(q, a, Х), где Х - магазинный символ из Г. Кроме того, результатом работы этой функции является пара (p, г), где p - новое состояние, г - новая цепочка символов, помещаемая в магазин вместо Х.

Графическое представление МП-автоматов может выполняться так же, как и для КА, с использованием диаграммы переходов. Однако, необходимость отмечать состояние магазина, вносит изменения в результирующий вид (рис. 4). Дуги помечаются строками вида a, X/б, где a - поступивший символ, Х - символ на вершине магазина, б - заменяющая цепочка.

Рисунок 4. Диаграмма переходов МП-автомата.

1.1.2 Классические проблемы

Проблема в теории автоматов в общем смысле заключается в определении принадлежности какому-либо языку. При формировании требований к программируемой системе поставлена задача реализации возможности решать конкретные упражнения. В сборнике Лукина и Чернышова [9] подробно рассмотрены многие из них, приведены алгоритмы решения.

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

· задание КА диаграммой, таблицей переходов, грамматикой с правилами, цепочками;

· задание грамматики через КА, правила, регулярное выражение;

· преобразования между автоматами, грамматиками и выражениями;

· операции с грамматиками и автоматами: минимизация, устранение левой рекурсии, е-правил и переходов, детерминизация;

· вывод последовательности конфигураций автомата;

· проверка допустимости цепочек.

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

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

Алгоритмы решения необходимого минимума реализуемых задач рассмотрены подробно в главе 2 «Формализация алгоритмов решения задач».

1.2 Существующие программные аналоги

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

1.2.1 JFLAP

Нельзя переоценить вклад группы разработчиков из университета Дьюка, длительное время занимающейся системой JFLAP (Java Formal Languages and Automata Package), свободным ПО, разработанным для образовательных целей в области теории автоматов и грамматик. Начиная с публикации “FLAP: A Tool for Drawing and Simulating Automata” [10] впервые на практике применён экспериментальный подход к обучению с использованием интерактивного инструмента FLAP, который высоко оценивается студентами: «мы наблюдали больше энтузиазма при изучении теории автоматов, чем в предшествующих семестрах, когда студенты решали задания с помощью карандаша и бумаги, не имея возможности протестировать разработку» (пер. с англ. “we have seen more enthusiasm for learning automata theory that in previous semesters when students wrote similar assignments using pencil and paper, not being able to test out their designs”). Многие источники с тех пор отмечали эффективность JFLAP [11, 12, 13] и поддерживали идею интерактивного подхода к преподаванию с помощью этого программного пакета. Проект получил развитие, был переписан на JAVA и существует до сих пор, ему посвящаются новые публикации несмотря на то, что с момента появления прошло не менее 20 лет. Непрекращающееся влияние JFLAP подтолкнуло разработчиков к изданию монографии [14] в 2006 году, в которой содержатся примеры работы с JFLAP, параметры симуляции, возможности программы и базовые знания об изучаемой научной области.

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

1.2.2 ReFaM

ReFaM (Rational Expressions and Finite Automata Minimization) -- кросс-платформенная программа с открытым исходным кодом, написанная на языке C++ на основе OpenMP и MPI и предназначенная для минимизации НКА [15]. Отечественные исследователи Цыганов, Винокуров и Ведин [16] отмечали, что отличительной чертой этого ПО является не только описание процесса минимизации в деталях, но и сбор статистики на каждом этапе. Однако, программа имеет слабый уровнем документированности и не обладает графическим интерфейсом.



1.2.3 Web-тренажёр Л. Чернышова

Разработанный в 2013 [17], русскоязычный тренажёр соответствует заявленной образовательной цели. К примеру, он имеет несколько режимов работы (обучение, тренировка, контроль) и ряд функциональных возможностей, близких к JFLAP, но должна быть доработана, чтобы соответствовать желаемому функционалу в полной мере.

1.2.4 COCO/R

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

1.2.5 Yakindu

Yakindu Statechart Tools - кроссплатформенная программа c открытым исходным кодом на платформе Eclipse для построения событийно-управляемых систем на основе конечных автоматов. Комбинирует текстовый и визуальный подход к моделированию систем, проводит синтаксическую и семантическую проверку конечных автоматов и генерирует код на Java, C или C++. По сравнению с COCO/R, имеет меньше доступных языков, но позволяет создавать исполняемые модели с помощью встроенного симуляционного движка.

1.2.6 Ragel

Ragel State Machine Compiler - компилятор конечных автоматов, написанный на С++, производящий исходный код на С, С++ или языке ассемблера. На вход принимаются регулярные выражения. Не обладает пользовательским графическим интерфейсом, но поддерживает визуализацию сгенерированного автомата посредством пакета автоматической визуализации графов Graphwiz. Преимуществом Ragel является возможность внесения пользовательских изменений в произвольные переходы конечного автомата с помощью встроенных (inline) в регулярные выражения операторов. Ragel также относят к парсерам.

1.2.7 Stateflow

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

Выводы из раздела

Поскольку каждое из выявленных решений имеет собственные недостатки и не отвечает поставленным задачам в полной мере, будет разработана новая. Её ключевыми особенностями станут: возможность решать широкий спектр типовых задач теории автоматов и грамматик (аналогично JFLAP), русскоязычность (как у web-тренажёра Чернышова), визуальный графический интерфейс (JFLAP, Yakindu), динамическое отображение результатов (JFLAP и Stateflow), нацеленность на образование и возможность генерации отчётов в электронной форме.

Как стало видно при анализе существующих решений, реализовать поддержку конечных автоматов и регулярных выражений можно различными способами, в том числе - встроенными средствами современных языков программирования. В работы поддерживается принцип разумного применения существующих решений, что подразумевает отказ от программирования громоздких собственных программных блоков при наличии готовых системных методов. Как упоминается в Главе 3, для практической реализации был выбран язык C# на фреймворке .Net, что предоставляет доступ к широкому множеству готовых методов и классов (в библиотеке System). Таким образом, основной деятельностью настоящей работы является не столько разработка уникальных алгоритмов, сколько подбор и компоновка на выбранном языке программирования и обеспечение достаточного пользовательского интерфейса.

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



2. Формализация алгоритмов решения задач

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

2.1 Классические алгоритмы решения

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

1. Преобразование КА в детерминированный.

2. Построение регулярной грамматики по выражению.

3. Построение регулярной грамматики по КА.

4. Построение регулярного выражения по грамматике.

5. Построение КА по грамматике.

6. Построение КА, допускающего определённые бинарные цепочки.

7. Построение МП-автомата по КС-грамматике.

8. Построение КС-грамматики по языку.

9. Построение ДМП-автомата по языку.

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

2.1.1 Преобразование КА в ДКА

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

Задача такого преобразования является одной из классических задач теории автоматов и особенно важна при программировании контроллеров, обработке текстов и других видах деятельности, где важна строгая регламентация порядка действий. Недетерминированный КА допускает неопределённый результат функции д(q, a). На практике считается, что НКА “размножается” при таком переходе, т.е. создаются копии автомата, из которых хотя бы одна должна прийти в конечное состояние. НКА используется на ранних стадиях проектирования, поскольку упрощает формализацию, но при работе над конкретными программами неприменим, поскольку создаваемые копии будут множиться и чрезмерно расходовать память [18].

Для преобразования НКА в ДКА применяется алгоритм К. Томпсона. В формальном виде он выражается так:

Пусть дан НКА ( Q, У, д: QЧУ>2Q, q0 Q, F Q ).

Цель: эквивалентный ДКА ( Q', У, д': Q'ЧУ>Q', q0' Q', F' Q' ), где:

Q' = {q' | q' 2Q},

q0' = {q0},

F' = {q Q' | p F: p q},

д'(q, a) = {д(c,a) | c q}.

Алгоритм Томпсона в менее формальном виде:

1. Помещаем в очередь Q множество, состоящее только из стартовой вершины.

2. Пока Q ? ш:

2.1. Достать из Q множество q

2.2. Для ?a У, если д(q, a) Q, то помещаем д(q, a) в Q.

2.3. Если q0 q : q0 F, то д(q, a) F'.

Для указанного алгоритма верхняя оценка времени работы -- O(n?2n), поскольку количество подмножеств множества состояний НКА меньше или равно 2n, и каждое их них обрабатывается один раз (O(n)). Такая скорость работы допустима для учебных целей.

2.1.2 Построение регулярной грамматики по выражению

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

1. Прообраз порождающего правила: S > б, S - начальный терминал.

2. На каждом следующем этапе анализируется вид остаточной части выражения,:

2.1. Оператор конкатенации. Если правило имеет вид A > aв, правило заменяется на A > aB, B > в, где B - новый нетерминал.

2.2. Оператор объединения. Если правило имеет вид A > {б1|б2}в, правило заменяется на A > б1в, A > б2в.

2.3. Оператор «звёздочка». Если правило имеет вид A > {б1}*в, правило заменяется на A > aв, A > в.

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

2.1.3 Построение регулярной грамматики по КА

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

1. T = ?.

2. N = Q\{q0}, т.е. каждый нетерминал находится во взаимно однозначном соответствии с неким A ? Q.

3. ? A Q, ? a ? правило перехода зависит от результата (A,a).

3.1. Если д(A,a) = , то ничего не выполняем.

3.2. Если д(A,a) = {B1, B2, …, Bn}, n > 0, то ? Bi:

3.2.1. Если A = q0, добавляем правило Bi > a.

3.2.2. Если A ? q0, добавляем правило Bi > Aa.

4. Если |F| = 1, F = {F0}, то S = F0; иначе, если F = {F1, F2, … , Fn}, n > 1, тогда S: N = N {S}, добавляются правила: S > F1 | F2 | ... | Fn.

На этом алгоритм завершает работу.

2.1.4 Построение регулярного выражения по грамматике с правилами

Регулярное выражение строится по регулярной грамматике. Для преобразования правил грамматики в формат выражения можно воспользоваться алгоритмом, использующимся в COCO/R, где последовательно выполняются такие действия:

1. Привести правила грамматики в единый формат.

2. Повторять последовательность, пока не останется единственный нетерминал:

2.1. Раскрыть скобки в каждом из правил.

2.2. Группировать правила по нетерминалами.

2.3. Выразить нетерминал и подставить в другие правила.

2.1.5 Построение КА, допускающего язык, порождаемый грамматикой

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

Для выполнения преобразования требуется выполнить последовательность действий (считаем, что A, B N, a T, p, p' P):

1. Для ? p, p': p = A > a и ? p' = A > aВ, добавить в грамматику правило вида A > aС, где С - новый нетерминал.

2. q0 = S.

3. Q = N {C}.

4. Для продукций вида p = A > aB добавить правило перехода д(A,a) = B.

5. В множество заключительных состояний F войдут вершины B, определённые правилами вида A > aB : p = A > a.

6. Для правил вида S > е S F.

На этом алгоритм завершает работу.

2.1.6 Построение КА, допускающего цепочки из {0,1}*

Конкретные цепочки могут задаваться словесным описанием или регулярным множеством, к примеру: «длина цепочки чётная, число единиц нечётно» или (1* + 01).

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

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

2.1.7 Построение МП-автомата по КС-грамматике

МП-автомат является эквивалентным КС-грамматике, если язык, допускаемый автоматом, совпадает с языком, порождаемым этой грамматикой.

Цель: МП-автомат с определением M = (Q, ?, Г, д, q0, Z0, F). Алгоритм построения будет следующим:

1. Q = {q0}, где q0 - единственное состояние. ? = T, Г = T N, Z0 = S.

2. ? p P правило перехода д добавляется в двух случаях:

2.1. Для всех p = A > б добавить правило qеA > qб.

2.2. Если p = A > a, где a T, то добавить правило qaa > qе.

Конец алгоритма.

2.1.8 Построение КС-грамматики для языка, заданного выражением

МП-автомат является эквивалентным КС-грамматике, если язык, допускаемый автоматом, совпадает с языком, порождаемым этой грамматикой.

2.1.9 Построение ДМП-автомата по языку

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

1. ? q Q, a У ? {е}, X Г ? д(q, a, X) имеет не более одного элемента - д : QЧУ ? {е}ЧГ > QЧГ*.

2. Если a У : д(q, a, X) ? , то д(q, е, X) = .

В случае наличия е-переходов или множественных переходов от них избавляются (допускается только правило S > е при условии, что S не встречается в правых частях правил).

Для устранения е-правил из грамматики используется алгоритм:

1. Составить B - множество всех е-порождающих нетерминалов.

2. ? p P : p = A > б0B1б1B2б2…Bkбk, где бi - любые, Bj B) добавить все возможные варианты правил с присутствием и отсутствием Bj.

3. Простые е-правила (вида A > е) удаляются.

4. Если в исходной грамматике выводился е, добавляется новый нетерминал и правило S' > S|е.



2.2 Графическое описание системы

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

2.2.1 Диаграмма прецедентов

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

Рисунок 5. Основные элементы диаграммы прецедентов

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

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

Таблица 2. Действия в различных режимах системы

Действие	S	T
Просмотреть каталог задач	+	+
Воспроизвести решение задачи	+	+
Решить задачу	+	+
Добавить новую задачу		+
Конструировать задачу		+
Сохранить отчёт по задаче	+	+
Открыть отчёт по задаче	+	+
Автоматически проверить решение	+	+
Изучить теоретический материал	+
Править теоретический материал		+
Изменить режим работы	+	+

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

2.2.2 Диаграмма последовательностей

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

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



2.2.3 Диаграмма классов

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

2.2.4 Диаграмма состояний

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

В данной системе смену состояний вызывают, в основном:

· смена режима преподаватель/студент;

· процесс выбора действий (переключение вкладок интерфейса);

· вход в режим теории и выход из него.

Выводы из раздела

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

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

3. Практическое решение целевых задач

3.1 Обоснование выбора средств программирования

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

3.1.1 Общие замечания и архитектура

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

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

3.1.2 UML

UML (Unified Modeling Language) - специфицированный язык графического моделирования [19]. Согласно нотации UML, любой процесс или система могут быть представлены в виде диаграмм различного уровня. На основе этих диаграмм впоследствии может быть автоматически сгенерирован код описываемой системы.

Значимыми особенностями UML являются:

· поддержка различных уровней абстракции;

· спецификация, позволяющая сконцентрироваться на структуре, а не соблюдении правил;

· применение интуитивно понятных элементов (пиктограмм, графических примитивов, стрелок взаимодействия) для передачи идеи;

· разделение диаграмм на концептуальные уровни.

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

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

· Диаграмма вариантов использования (use case diagram)

· Диаграмма классов (class diagram)

· Диаграммы поведения (behavior diagrams)

o Диаграмма состояний (statechart diagram)

o Диаграммы взаимодействия (interaction diagrams)

§ Диаграмма последовательности (sequence diagram)

3.1.3 Windows

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

Тестирование проводилось на версии системы Windows 8.1 64bit. При этом, проектирование производилось с допущением портирования на другие платформы, в будущем возможно развитие проекта для использования на системах других семейств, в том числе и мобильных.

3.1.4 Объектно-ориентированное программирование

Парадигма объектно-ориентированного программирования (ООП) в настоящее время распространена беспрецедентно широко (такие коммерчески успешные языки, как Java, C# и Python, поддерживают её).

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

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

3.1.5 С# и .NET Framework

C# - один из языков ООП. Несмотря на наличие ряда недостатков [21], при кратком сравнении был выбран именно этот язык по ряду причин:

· удобные средства разработки под Windows при поддержке Microsoft, библиотеки .NET;

· наличие многочисленной и качественной документации;

· усиленная поддержка всех концепций ООП;

· возможности кроссплатформенности;

· оптимизированность основных готовых модулей;

· лаконичность языка и простота разработки;

· наличие сборщика «мусора»;

· личные предпочтения.

Программная платформа .NET - это фреймворк от компании Microsoft. Основная цель применения в данном проекте - способствовать созданию визуального облика программной системы из готовых компонентов графической системы Windows Forms в составе .NET Framework.

WinForms представляют собой обёртку вокруг Win32 API в управляемом коде и применяется для разработки интерфейса программы. При данном подходе отрисовка объектов происходит посредством GDI/GDI+, что не требует генерации громоздких конструкций и длительных сроков изучения технологии, как, например, в WPF (Windows Presentation Foundation) - альтернативном подходе, при для отрисовки применяется DirectX. WinForms предпочтительна для данной работы, так как, помимо требований наличия DirectX и сложностей разработки, в WPF отсутствует поддержка кроссплатформенности.

В настоящее время .NET Framework развивается как .NET Core, ориентированный на кроссплатформенность, что является плюсом.

3.1.6 Visual Studio Community

В качестве среды разработки выбрана Visual Studio Community 2017 (далее - VS) от компании Microsoft [22].

Основные причины выбора данной среды:

· Производительность. Быстрая разработка, сборка, набор отладчиков, редакторов и инструментов диагностики в одном месте;

· Экосистема. VS предоставляет доступ к различным расширениям и библиотекам .Net;

· Мощные инструменты программирования. Поддержка синтаксиса, IntelliSense, рефакторинг;

· Интеграция с Git (популярная система контроля версий)/Github;

· Открытая удобная справочная система (веб-версия и интегрированная);

· Доступность. Microsoft разрешает бесплатное некоммерческое использование данного продукта.

3.2 Основные программные модули

В структуре проекта присутствуют: класс для выбора решаемой задачи; класс для сохранения данных в файле; интерфейс IShowable, указывающий на классы, предназначенные для записи в файл; два основных класса, реализующих IShowable, для сущностей «Конечный автомат» и «Грамматика».

...