Автор: Кристоф Нойманн
Перевод: Березовская Е.А.
Источник: https://www.researchgate.net/publication...
В этой статье рассматриваются три метода преобразования детерминированных конечных автоматов (DFA) в регулярные выражения и сравнивается полезность каждого метода. Обследуемыми методами являются метод транзитивного закрытия, метод удаления состояний и алгебраический метод Бжозовского.
Основная статья Клини определяет регулярные выражения и их связь с конечными автоматами. Клини доказывает эквивалентность конечных автоматов и регулярных выражений, тем самым предоставляя нам первый метод – транзитивный метод замыкания для преобразования детерминированных конечных автоматов (ДКА) в регулярные выражения. Позже Бжозовский расширил метод Клини, введя понятие производных регулярных выражений, но его статья не была оцененан должным образом, пока Г. Берри и Р. Сетхи не вывели на передний план статью Бжозовского в. Метод удаления состояний представлен в, но Линц представляет более простой метод в.
Мы будем использовать модель Мура для конечных автоматов. Для автомата M с входным алфавитом Ak = {0, 1, ···, k - 1} M имеет m состояний Ms = {q1, q2, ···, qm}, где q? – начальное состояние M и Mf = {qf1, qf2, ···, qfn} – n конечных состояний M, где n ? m. Для ясности мы будем использовать буквы для представления каждого значения в алфавите А вместо использования числового представления (a = 0, b = 1, и т.д.), а для удобства предположим, что q1 является исходным состоянием, если не указано иное.
Мы будем использовать определение Клини регулярных выражений. Регулярные выражения определяются рекурсивно как:
Регулярные выражения в правиле 1 – терминалы. Конкатенация терминалов – это строка. Для данного регулярного выражения x существует множество X, которое содержит все строки, представленные x. Мы будем использовать x и X взаимозаменяемо. Одна строка просто представлена набором, содержащим эту единственную строку.
Так как + коммутативна, применяются все коммутативные версии.
Предположим, что данный ДКA M должен быть представлен как регулярное выражение
Рассмотрим автомат на рисунке 1. Вход для ребра в автомат является регулярным выражением. Достаточно просто, что регулярное выражение для перехода от q1 к q2 равно b, переход от q2 к q3 равен c и т.д. Более того, регулярное выражение, представляющее переход от q1 к q3, является конкатенацией регулярных выражений, образующих bc. Таким образом, мы можем найти регулярное выражение для автомата bca, так как это выражение является конкатенацией всех переходов из начального состояния q1 в конечное состояние q4
В более общем плане, для пути от q? до qf, конкатенация регулярного выражения для каждого перехода в пути образует регулярное выражение, которое представляет ту же строку, что и путь от q? до qf в автомате. Предположим, что существует единственный единственный путь в автомате M из q? до qf, существует только одно регулярное выражение R такое, что R представляет ту же строку, что и ДКA M. Однако это тривиальный автомат, рассмотрим, как развернуть его в более общий случай.
Теперь рассмотрим ДКА на рисунке 2. Ясно, что между q1 и q2 существует несколько путей. Мы не можем получить простое регулярное выражение для представления ДКА, однако, используя другие операторы (объединение и итерация), мы можем опираться на наш предыдущий подход для создания конструкции, которая работает для всех типов ДКА. Мы откажемся от доказательства и оставим его Клини. Доказательство также продемонстрировано Хопкрофтом и Ульманом и достаточно ясно объяснено Саломаа.
Предположим, что регулярное выражение Rij представляет собой совокупность всех строк, которые переводят автомат M из qi в qj. Кроме того, предположим, что представляет множество всех строк, которые переводят автомат M из qi в qj, не проходя через любое состояние выше qk. Мы можем построить Rij путем последовательного построения.
Как мы видим, эта последовательная конструкция создает регулярные выражения, пока мы не получим Rij. Затем мы можем построить регулярное выражение, представляющее M как объединение всех R?f, где q? – начальное состояние и f ? Mf (конечные состояния для M).
Этот метод похож по характеру на проблему с парными краткими путями. Единственное отличие состоит в том, что мы принимаем объединение и конкатенацию регулярных выражений вместо суммирования расстояний. Это решение имеет ту же форму, что и транзитивное замыкание, и относится к совокупности задач, связанных с замкнутыми полукольцами.
Основная проблема подхода транзитивного замыкания состоит в том, что он создает очень большие регулярные выражения. Изучая формулу для , ясно, что значительная длина обусловлена повторным объединением конкатенированных терминов. Даже используя предыдущие идентификаторы, мы все еще имеем длинные выражения.
Подход удаления состояния определяет шаблоны внутри графика и удаляет состояния, создавая регулярные выражения вдоль каждого перехода. Преимущество этого метода в отношении метода транзитивного закрытия заключается в том, что его легче визуализировать. Этот метод описан Ду и Ko, но мы рассмотрим гораздо более простой подход, который дает Линц.
Во-первых, любые мульти-ребра объединены в одно ребро, которое содержит объединение входов. Предположим, что от q2 до q5 существует ребро a и ребро b, которые будут объединены в одно ребро q2 до q5, которое имеет значение a + b.
Теперь рассмотрим подграф автомата M, который имеет вид, приведенный на рисунке 3. Состояние q может быть удалено, и автомат может быть приведен к форме на рисунке 4. Шаблон может по-прежнему применяться, если края отсутствуют. Для края, который отсутствует, опустить соответствующий край на рисунке 4.
Этот процесс повторяется до тех пор, пока автомат имеет вид, как на рисунке 5. Затем путем непосредственного расчета, регулярное выражение становится равно:
Метод Бжозовского [3] использует уникальный подход к генерации регулярных выражений. Мы создаем систему регулярных выражений с одним регулярным выражением, неизвестным для каждого состояния в M, а затем мы решаем систему для R?, где R? – регулярное выражение, связанное с начальным состоянием q?. Эти уравнения являются характеристическими уравнениями М.
Мы используем это уравнение для выделения Ri по левому размеру и последовательно подставляем Ri в другое уравнение. Мы повторяем этот процесс, пока не найдем R? без каких-либо неизвестных с правой стороны.
Метод удаления состояний представляется полезным для определения регулярных выражений посредством ручного контроля, но не так просто реализeем в качестве транзитивного подхода закрытия и алгебраического подхода. Переходный подход закрытия дает ясную и простую реализацию, но имеет тенденцию создавать очень длинные регулярные выражения. Алгебраический подход является элегантным, опирается на рекурсивный подход и генерирует достаточно компактные регулярные выражения. Метод Бжозовского особенно подходит для рекурсивно ориентированных языков, таких как функциональные языки, где переходный подход закрытия будет громоздким для реализации.