Algorithms

1. Построение ε-NFA/NFA из регулярного выражения

Алгоритм Томпсона

• Первая формальная публикация идеи построения ε-NFA из регулярных выражений

• Строит автомат с ε-переходами

• Рекурсивная конструкция на основе структуры выражения

• Programming Techniques: Regular expression search algorithm | Communications of the ACM

• Thompson's construction - Wikipedia

Алгоритм Глушкова

• Построение NFA без ε-переходов напрямую из регулярного выражения

• Использует позиции символов в выражении

• Более компактные автоматы по сравнению с конструкцией Томпсона

• Glushkov V. M., "The abstract theory of automata", Russian Math. Surveys, 16:5 (1961), 1–53

2. Построение DFA из NFA

Алгоритм: Subset Construction

• Каждое состояние DFA соответствует множеству состояний NFA

• Алгоритм строит все достижимые множества состояний NFA

• Детерминизация устраняет неоднозначность переходов

• Finite Automata and Their Decision Problems | IBM Journals & Magazine | IEEE Xplore

3. Минимизация DFA

Алгоритм Хопкрофта

• Разделяет состояния DFA на классы эквивалентности
• Оптимальная асимптотическая сложность: O(n*logn)
• Наиболее эффективный алгоритм на практике

Алгоритм Бржозовского

• Минимизация через двойное обращение (реверс) DFA

• Прост в реализации

• Может иметь экспоненциальную сложность в худшем случае

• DFA minimization - Wikipedia

Общие ресурсы:

• Intro To Automata Theory, Languages And Computation, 2ed - Hopcroft, Motwani, Ullman Разделы 2.2–2.4, 4.6 — Томпсон, subset construction, минимизация.

4. Отрисовка графа

• https://tikz.dev/gd-overview
• https://www.graphviz.org/
• https://coderivers.org/blog/graphviz-python/
• https://github.com/pygraphviz/pygraphviz?ysclid=mi5c6muuou859231319

Graphviz — это система визуализации графов, которая автоматически преобразует текстовое описание структуры графа в изображение. Graphviz применяет различные алгоритмы раскладки, определяя координаты вершин и форму рёбер так, чтобы граф выглядел как можно проще. Затем структура графа отображается в различные форматы, такие как PNG, SVG или PDF.

• https://rdrr.io/cran/igraph/man/

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

• https://networkx.org/documentation/stable/tutorial.html
• https://github.com/networkx/networkx

NetworkX — это простая и удобная Python-библиотека для работы с графами, подходящая для моделирования ДКА и НКА. Её основное преимущество — простота, а недостаток — низкая производительность на больших графах.

5. Метод исключения состояний (State elemination)

Алгоритм: Постепенное удаление узлов графа Автомат преобразуется в Обобщенный НКА (GNFA), где переходами являются регулярные выражения. Состояния удаляются по одному, а пути через удаленное состояние заменяются эквивалентным регулярным выражением. Последовательно применяется формула: $R_{new} = R_{old} \cup (R_{pq} \cdot (R_{qq})^* \cdot R_{qr})$.

https://www.geeksforgeeks.org/theory-of-computation/generating-regular-expression-from-finite-automata/

6. Алгебраический метод (Arden's theorem)

Алгоритм: Решение системы уравнений Для каждого состояния составляется уравнение зависимости от других состояний на основе переходов. Система решается относительно начального состояния с использованием правила: если $X = AX \cup B$, то $X = A^*B$.

https://www.geeksforgeeks.org/theory-of-computation/generating-regular-expression-from-finite-automata/

7.Алгоритм Клини (Динамическое программирование)

Алгоритм: Рекурсивное построение путей Метод аналогичен алгоритму Флойда-Уоршелла для поиска кратчайших путей. Вычисляется $R_{ij}^{(k)}$ — регулярное выражение для путей из $i$ в $j$, проходящих только через состояния из множества ${1, \dots, k}$.Формула: $R_{ij}^{(k)} = R_{ij}^{(k-1)} \cup (R_{ik}^{(k-1)} \cdot (R_{kk}^{(k-1)})^* \cdot R_{kj}^{(k-1)})$.

https://en.wikipedia.org/wiki/Kleene%27s_algorithm