Оглавление

• О проекте
• Сборка и запуск
• Генерация случайных тестов
• Синтаксис входных данных
• Функции преобразователя

Если останутся вопросы по функциональности, задайте их здесь

О проекте

Принцип работы — на вход даётся файл с операциями над объектами, на выходе генерируется latex-файл с подробным описанием выполненных преобразований.

ВАЖНО! Для корректного составления latex-файла нужно поставить Graphviz, чтобы в системе поддерживалась команда dot. Без этого не будет работать генерация изображений автоматов.

Если в системе поддерживается команда pdflatex, то тогда сразу будет генерироваться отчет в виде pdf-документа. Если нет, необходимо установить Latex.

Сборка и запуск

Сборка осуществляется через cmake. В wiki есть пример, как можно собрать.

Для запуска надо перейти в корневую папку проекта и там запустить собранное приложение. Пример на windows:

.\build\apps\InterpreterApp\Debug\InterpreterApp

В качестве опционального аргумента указывается путь к файлу с командами (по умолчанию test.txt).

Генерация случайных тестов

Для удобства тестирования был создан генератор входных данных.
Его запуск на windows:

.\build\apps\InputGeneratorApp\Debug\InputGeneratorApp

В файле apps\InputGeneratorApp\src\main.cpp можно поменять параметры генерируемых тестов:
TG.generate_task(3, 5, false, false);
где 1 аргумент - количество операций, 2 аргумент - максимальное количество функций в последовательности.

Синтаксис входных данных

Типизация

Интерпретатор поддерживает следующие типы:

• Regex — регулярное выражение (с операциями '|' и '*')
• NFA — недетерминированный конечный автомат
• DFA — детерминированный конечный автомат
• PrefixGrammar - префиксная грамматика
• BRefRegex - расширенные регулярные выражения с обратными ссылками
• MFA - конечный автомат с памятью
• Int
• String
• Boolean
• OptionalBool
• AmbiguityValue - мера неоднозначности
  (Может принимать одно из 4-х значений: Unambiguous, Almost unambiguous, Polynomially ambiguous, Exponentially ambiguous)
• Array - правила переписывания

Синтаксические конструкции

• Regex. Записываются в фигурных скобках. Пример: {a*(b|c)*}
• RandomRegex. Символ *. на место которого подставляются генерируемые регулярные выражения в верификаторе
• Array. Правила переписывания. Пример: [[{a} {b}]] (означает a -> b)
• Function. Название и список аргументов через пробел. Пример: Glushkov {ab|a}
• Function sequence. Последовательное применение функций справа-налево. Пример: Annote.Glushkov.DeAnnote {a}
• Int. Целое число. Пример: 8
• Variable - переменная. Примеры: A, N1, N2
• Expression. Function sequence, Int, Regex или Variable

Для функций и последовательностей функций должны выполняться соответствия типов. Больше про типы функций - ниже в разделе Функции преобразователя.

Команды

В каждой строчке записана ровно одна команда. Поддерживаются команды пяти типов:

• declaration
  Присвоение переменной значения. Если в конце стоит !!, выражение логируется в latex.
  Синтаксис:
  <varaible> = <expression> '!!'?
  Пример:

    A = Complement.Annote (Glushkov {a*}) !!
    B = States.Reverse A
  

• test
  Аргументы:
  1. НКА или регулярное выражение (язык 1)
  2. регулярное выражение — тестовый сет (язык 2)
  3. натуральное число — шаг итерации в сете
  Подробнее про то, как работает — см. в презентации.
  Синтаксис:
  Test <expression> <expression> <int>
  Пример:

    Test {(aa)*} {a*} 3
    Test (Glushkov {(aa)*}) {a*} 1
  

• predicate
  Булева функция, записанная одной строчкой. Будет логироваться в любом случае.
  Синтаксис:
  <function> <expression>+
  Пример:
  Equiv (Antimirov {ab|a}) (Glushkov {ab|a})

• verify
  Аргументы:
  1. Предикат (с конструкцией *, на место которой подставляются сгенерированные регулярные выражения)
  2. (опциональный) натуральное число — количество тестов
  Синтаксис:
  Verify <expression> <int>?
  Пример:

    Verify (Equal (Ambiguity.Glushkov.Arden.Glushkov *) (Ambiguity.Glushkov *))
  

• set
  Аргументы:
  1. Имя флага:
  - weak_type_comparison — устанавливает эквивалентность типов DFA и NFA, т.е. допускает на вход NFA для функций, требующих DFА
  TODO:
  - log_theory — добавляет теоретический блок к функциям в отчете
  - auto_remove_trap_states — отвечает за удаление ловушек
  2. Значение флага: true / false
  Синтаксис:
  Set <flagName> <true/false>

Функции преобразователя

* NFA здесь можно понимать как FA, для которого не обязан быть включённым флаг детерминизма.

Преобразования со сменой класса:

• Thompson: Regex -> NFA — строит автомат Томпсона по регулярному выражению
• Antimirov: Regex -> NFA
• Glushkov: Regex -> NFA
• IlieYu: Regex -> NFA — follow-автомат
• Arden: NFA -> Regex — строит регулярное выражение по автомату
• PrefixGrammar: NFA -> PrefixGrammar — возвращает префиксную грамматику для НКА
• PGtoNFA: PrefixGrammar -> NFA — преобразует префиксную грамматику в НКА

Преобразования внутри класса

Над регулярными выражениями:

• Linearize: Regex -> Regex — размечает буквы в регулярном выражении, как в алгоритме Глушкова
• DeLinearize: Regex -> Regex — снимает разметку Linearize
• DeAnnote: Regex -> Regex — снимает разметку Annote
  TODO:
• Disambiguate: Regex -> Regex — для 1-однозначных языков возвращает 1-однозначное регулярное выражение, для остальных возвращает данное на вход

Над конечными автоматами:

• Determinize: NFA -> DFA — детерминизация без добавления состояния-ловушки
• Minimize: NFA -> DFA — минимизация без добавления состояния-ловушки
• Determinize+: NFA -> DFA — детерминизация с добавлением состояния-ловушки
• Minimize+: NFA -> DFA — минимизация с добавлением состояния-ловушки
• RemoveTrap: DFA -> DFA - удаление состояний-ловушек
• Reverse: NFA -> NFA — обращение ("переворачивает" автомат)
• Complement: DFA -> DFA — дополнение
• RemEps: NFA -> NFA — удаление ε-правил
• MergeBisim: NFA -> NFA — объединение эквивалентных по бисимуляции состояний
• Annote: NFA -> DFA — навешивает разметку на все буквы в автомате, стоящие на недетерминированных переходах
• DeAnnote: NFA -> NFA — снимает разметку Annote
• DeLinearize: NFA -> NFA — снимает разметку Linearize
• Intersect: (NFA, NFA) -> NFA — пересечение языков
• Union: (NFA, NFA) -> NFA — объединение языков
• Difference: (NFA, NFA) -> NFA — разность языков

Многосортные функции

• States: NFA -> Int — возвращает количество состояний в автомате
• ClassCard: NFA -> Int — число классов эквивалентности в трансформационном моноиде
• ClassLength: NFA -> Int — самое длинное слово в классе эквивалентности трансформационного моноида
• MyhillNerode: NFA -> Int — возвращает число классов эквивалентности по Майхиллу–Нероуду
• GlaisterShallit: NFA -> Int — определяет нижнюю границу количества состояний в НКА для языка
• Ambiguity: NFA -> AmbiguityValue — определяет меру неоднозначности автомата. Если число путей, по которым распознается слово (длины от минимальной до $s^2$) растёт быстрее, чем полином степени |s|, где s — число состояний НКА, то автомат экспоненциально неоднозначен. Если число путей растёт медленнее, чем линейная функция, то автомат почти однозначен (либо однозначен, если путь всегда один). Иначе автомат полиномиально неоднозначен.
  TODO:
• PumpLength: Regex -> Int — возвращает длину накачки языка
• Normalize: (Regex, Array) -> Regex
• Normalize: (Regex, FileName) -> Regex

Предикаты

Для регулярных выражений:

• Subset: (Regex, Regex) -> Boolean — проверяет вложенность второго языка в первый
• Equiv: (Regex, Regex) -> Boolean — проверяет, описывают ли регулярные выражения один язык
• OneUnambiguity: Regex -> Boolean — проверяет, является ли регулярное выражение 1-однозначным. Регулярное выражение является 1-однозначным, если возможно однозначно определить, какая позиция символа в регулярном выражении должна соответствовать символу во входном слове, не заглядывая за пределы этого символа во входном слове.
• Equal: (Regex, Regex) -> Boolean — проверяет буквальное равенство регулярных выражений (как строк, с учетом альтернатив)

Для конечных автоматов:

• Bisimilar: (NFA, NFA) -> Boolean — проверяет бисимилярность автоматов
• Equiv: (NFA, NFA) -> Boolean — проверяет, описывают ли автоматы один язык
• Equal: (NFA, NFA) -> Boolean — проверяет буквальное равенство автоматов
• Subset: (NFA, NFA) -> Boolean — проверяет вложенность второго языка в первый
• Minimal: DFA -> Boolean — проверяет, минимален ли детерминированный автомат
• Minimal: NFA -> OptionalBool — проверяет, минимален ли недетерминированный автомат
• Deterministic: NFA -> Boolean — проверяет автомат на детерминированность
• OneUnambiguity: NFA -> Boolean — проверяет, является ли язык 1-однозначным. 1-однозначный язык - это язык, описываемый 1-однозначным регулярным выражением.
  TODO:
• SemDet: NFA -> Boolean — проверяет, является ли автомат семантически детерминированным. Язык состояния q — это {w | q→^wq_f} Семантическая детерминированность означает, что для всякой неоднозначности q _i →^aq_j1, ..., q_i→^aq_jk существует такое состояние q_js, что языки всех q_jt (1 ⩽ t ⩽ k) вкладываются в его язык.

Многосортные:

• Equal: (Int, Int) -> Boolean
• Equal: (Boolean, Boolean) -> Boolean
• Equal: (AmbiguityValue, AmbiguityValue) -> Boolean

Методы регулярных выражений с обратными ссылками:

• MFA: BRefRegex -> MFA
• MFAexpt: BRefRegex -> MFA
• Reverse: BRefRegex -> BRefRegex
• IsAcreg: BRefRegex -> Boolean

Методы MFA:

• RemEps: MFA -> MFA
• AddTrap: MFA -> MFA
• Complement: MFA -> MFA
• Deterministic: MFA -> Boolean
• Bisimilar: (MFA, MFA) -> OptionalBool
• Action: MFA -> NFA
• Symbolic: MFA -> NFA
• ActionBisimilar: (MFA, MFA) -> Boolean
• SymbolicBisimilar: (MFA, MFA) -> Boolean
• Equal: (MFA, MFA) -> Boolean
• MergeBisim: MFA -> MFA
• Equal: (BRefRegex, BRefRegex) -> Boolean

Метод Test

Test: (Regex|NFA, Regex, Int) -> таблица — порождает слова, принадлежащие второму языку (2 аргумент), раскрывая каждую итерацию Клини начиная с 0 (пустого слова) и увеличивая с каждым разом на заданное значение (3 аргумент). Если в регулярном выражении (для 2 языка) присутствуют альтернативы, то выбирается 1ая из них.
То есть
a*b c шагом 2 раскрывается в ряд: b, aab, aaaab ...
(a*b)*c c шагом 1 раскрывается в ряд: c, abc, aabaabc ...
Возвращает таблицу, в которой указаны результаты проверки на принадлежность каждого из порожденных слов первому языку (1 аргумент).
Завершает тестирование, когда сделано более 12 шагов, либо парсинг входной строки занимает больше 3 минут.

Верификатор гипотез

Verify: (Boolean, Int?) -> Int - принимает на вход набор действий, содержащий единственный предикат. Строится сет тестов, размер которого определяет 2й аргумент (значение по умолчанию - 20). В выражение на место конструкции * подставляются случайные регулярные выражения.
В результатах тестирования выделяется доля тестов с положительным значением предиката, и примеры кейсов, когда гипотеза не выполнилась.

Дополнительно о некоторых функциях и требованиях к входным данным можно почитать в файле.

Успехов!