Необходимо скачать предоставленное окружение и реализовать функцию dfa2re в файле task.cpp, принимающую в качестве аргумента детерминированный конечный автомат в виде DFA и возвращающую корректное регулярное выражение в виде std::string, задающее тот же язык, что и заданный автомат.
Окружение содержит реализации алфавита в виде класса Alphabet (этот класс позволяет автоматически получать алфавит, над которым задан автомат) и ДКА в виде класса DFA (этот класс помогает считать автомат в правильном формате). API этих классов приведен в файле api.hpp. Состояния в DFA идентифицируются непустыми строковыми именами, присваиваемыми им при создании.
Тестовые автоматы всегда корректны, детерминированы и задаются в следующем формате: на первой строке перечисляются все символы алфавита, затем на отдельных строчках перечисляются все состояния в формате "[имя_состояния]" или же "[[имя_состояния]]" для финальных состояний. Первое упомянутое состояние считается начальным. Затем перечисляются все переходы в автомате в формате "[имя_начального_состояния] символ_перехода [имя_конечного_состояния]", по одному переходу на строчку. Можно считать, что тестовые автоматы содержат не более 100 состояний.
Функция main в файле main.cpp считывает ДКА из файла dfa2re.in, передает его в функцию dfa2re, после чего выводит построенное регулярное выражение в текстовом виде в файл dfa2re.out. Регулярные выражения должны состоять из символов алфавита (в алфавит могут входить буквы латинского алфавита и цифры), скобок, | - операция объединения, * - итерация. Специальный символ пустой строки (эпсилон) не используется: выражение (ε|a)b* записывается как (|a)b*. Пустая строка считается регулярным выражением, задающим пустое слово, а не пустым регулярным выражением.
Сборка окружения выполняется с помощью CMake или bash-скрипта quick-setup.sh. Получаемый бинарный исполняемый файл - dfa2re.