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

Какие существуют алгоритмы для преобразования NFA в эквивалентные регулярные выражения? Есть ли преимущества в отношении сложности времени или размера результата?

^{Это должен быть справочный вопрос. Пожалуйста, включите общее описание вашего метода, а также нетривиальный пример.}

Есть несколько методов для преобразования конечных автоматов в регулярные выражения. Здесь я опишу тот, который обычно преподается в школе, который очень нагляден. Я считаю, что это наиболее используемый на практике. Однако написание алгоритма не такая хорошая идея.

Метод удаления состояния

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

Ключевая идея

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

Основную закономерность можно увидеть на следующих рисунках. Первый имеет метки между которые являются регулярными выражениями и мы хотим удалить .e , f , g , h , i $p,q,r$$e,f,g,h,i$$q$

После удаления мы составляем вместе (сохраняя остальные ребра между и но это не отображается на этом):p $e,f,g,h,i$$p$$r$

пример

Используя тот же пример, что и в ответе Рафаэля :

мы последовательно удаляем :$q_2$

а затем :$q_3$

тогда мы все еще должны применить звезду к выражению от до . В этом случае конечное состояние также является начальным, поэтому нам просто нужно добавить звездочку:q $q_1$$q_1$

Алгоритм

L[i,j]это регулярное выражение языка от до . Сначала мы удалим все мульти-ребра:q $q_i$$q_j$

for i = 1 to n:
  for j = 1 to n:
    if i == j then:
      L[i,j] := ε
    else:
      L[i,j] := ∅
    for a in Σ:
      if trans(i, a, j):
        L[i,j] := L[i,j] + a

Теперь состояние снятия. Предположим, мы хотим удалить состояние :$q_k$

remove(k):
  for i = 1 to n:
    for j = 1 to n:
      L[i,i] += L[i,k] . star(L[k,k]) . L[k,i]
      L[j,j] += L[j,k] . star(L[k,k]) . L[k,j]
      L[i,j] += L[i,k] . star(L[k,k]) . L[k,j]
      L[j,i] += L[j,k] . star(L[k,k]) . L[k,i]

Обратите внимание , что оба с карандашом бумаги и с помощью алгоритма вы должны упростить выражения , как star(ε)=ε, e.ε=e, ∅+e=e, ∅.e=∅(Под рукой вы просто не написать край , когда он не , или даже для самостоятельного цикла и вы игнорируете , когда есть нет перехода между и или и )$∅$$ε$q k q j q $q_i$$q_k$$q_j$$q_k$

Теперь, как использовать remove(k)? Вы не должны легко удалять окончательные или начальные состояния, иначе вы пропустите части языка.

for i = 1 to n:
  if not(final(i)) and not(initial(i)):
    remove(i)

Если у вас есть только одно конечное состояние и одно начальное состояние тогда конечное выражение будет:q $q_f$$q_s$

e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])

Если у вас есть несколько конечных состояний (или даже начальных состояний), то нет простого способа их объединения, кроме применения метода транзитивного замыкания. Обычно это не проблема вручную, но это неудобно при написании алгоритма. Гораздо более простой обходной путь - перечислить все пары и запустить алгоритм на графе (уже удаленном из состояния), чтобы получить все выражения предполагая, что является единственным начальным состоянием, а является единственным конечным состояние, то делает объединение всех .е с , е ы е д ы , $(s,f)$$e_{s,f}$$s$$f$$e_{s,f}$

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

Cons

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

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

метод

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

Пусть NFA без -переходов. Для каждого состояния создайте уравнениеε q $A= (Q,\Sigma,\delta,q_0,F)$$\varepsilon$$q_i$

$\qquad \displaystyle Q_i = \bigcup\limits_{q_i \overset{a}{\to} q_j} aQ_j \cup \begin{cases} \{\varepsilon\} &,\ q_i \in F \\ \emptyset &, \text{ else}\end{cases}$

где - множество конечных состояний, а означает, что существует переход от к помеченный . Если вы читаете как или (в зависимости от определения вашего регулярного выражения), вы видите, что это уравнение регулярных выражений.$F$$q_i \overset{a}{\to} q_j$$q_i$$q_j$$a$$\cup$$+$$\mid$

Для решения системы вам нужны ассоциативность и дистрибутивность и (конкатенация строк), коммутативность и лемма Ардена ¹:$\cup$$\cdot$$\cup$

Пусть регулярные языки с . Затем, ε ∉ $L,U,V \subseteq \Sigma^*$$\varepsilon \notin U$

$\qquad \displaystyle L = UL \cup V \quad \Longleftrightarrow \quad L = U^*V$

Решением является набор регулярных выражений , по одному на каждое состояние . описывает именно те слова, которые могут быть приняты при запуске в ; поэтому (если - начальное состояние) является искомым выражением.$Q_i$$q_i$$Q_i$$A$$q_i$$Q_0$$q_0$

пример

^{Для ясности мы обозначим одноэлементные множества по их элементу, то есть . Пример из-за Георга Зецше.$a = \{a\}$}

Рассмотрим это NFA:

^{[ источник ]}

Соответствующая система уравнений:

$\qquad \begin{align} Q_0 &= aQ_1 \cup bQ_2 \cup \varepsilon \\ Q_1 &= bQ_0 \cup aQ_2 \\ Q_2 &= aQ_0 \cup bQ_1 \end{align}$

Теперь вставьте третье уравнение во второе:

$\qquad \begin{align} Q_1 &= bQ_0 \cup a(aQ_0 \cup bQ_1) \\ &= abQ_1 \cup (b \cup aa)Q_0 \\ &= (ab)^*(b \cup aa)Q_0 \end{align}$

Для последнего шага мы применим лемму Ардена с , и . Обратите внимание, что все три языка являются регулярными и , что позволяет нам применять лемму. Теперь мы включим этот результат в первое уравнение:$L = Q_1$$U = ab$$V = (b \cup aa) \cdot Q_0$$\varepsilon \notin U = \{ab\}$

$\qquad \begin{align} Q_0 &= a(ab)^*(b \cup aa)Q_0 \cup baQ_0 \cup bb(ab)^*(b \cup aa)Q_0 \cup \varepsilon \\ &= ((a \cup bb)(ab)^*(b \cup aa) \cup ba)Q_0 \cup \varepsilon \\ &= ((a \cup bb)(ab)^*(b \cup aa) \cup ba)^* \qquad \text{(by Arden's Lemma)} \end{align}$

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

$\qquad \displaystyle ((a + bb)(ab)^*(b + aa) + ba)^*.$

Обратите внимание, что он довольно лаконичен (сравните с результатами других методов), но не определяется однозначно; Решение системы уравнений с другой последовательностью манипуляций приводит к другому - эквивалентно! - выражения.

1. Доказательство леммы Ардена см. Здесь .

Алгебраический метод Бжозовского

Это тот же метод, который описан в ответе Рафаэля , но с точки зрения систематического алгоритма, а затем и самого алгоритма. Оказывается, это легко и естественно реализовать, если вы знаете, с чего начать. Также это может быть проще, если рисовать все автоматы по какой-то причине нецелесообразно.

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

Идея алгоритма

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

Исходя из оригинального решения правила Ардена к уравнению языка мы можем рассматривать автомат как систему уравнений вида:$X=A^*B$$X=AX∪B$

мы можем решить это путем наведения на , обновив массивы и соответственно. На шаге имеем:$n$$A_{i,j}$$B_{i,j}$$n$

и правило Ардена дает нам:

и установив и мы получим:$B'_n = A_{n,n}^* B_n$$A'_{n,i}=A_{n,n}^*A_{n,i}$

и тогда мы можем удалить все потребности в системе, установив для :$X_n$$i,j<n$

Когда мы решили когда , мы получили уравнение, подобное этому:$X_n$$n=1$

без . Таким образом, мы получили наше регулярное выражение.$A'_{1,i}$

Алгоритм

Благодаря этому мы можем построить алгоритм. Чтобы иметь то же соглашение, что и в приведенной выше индукции, мы будем говорить, что начальное состояние - а число состояний - . Во-первых, инициализация для заполнения :$q_1$$m$$B$

for i = 1 to m:
  if final(i):
    B[i] := ε
  else:
    B[i] := ∅

и :$A$

for i = 1 to m:
  for j = 1 to m:
    for a in Σ:
      if trans(i, a, j):
        A[i,j] := a
      else:
        A[i,j] := ∅

а затем решение:

for n = m decreasing to 1:
  B[n] := star(A[n,n]) . B[n]
  for j = 1 to n:
    A[n,j] := star(A[n,n]) . A[n,j];
  for i = 1 to n:
    B[i] += A[i,n] . B[n]
    for j = 1 to n:
      A[i,j] += A[i,n] . A[n,j]

окончательное выражение тогда:

e := B[1]

Реализация

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

Метод транзитивного закрытия

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

Ключевая идея

Пусть представляет регулярное выражение для строк, идущих от к используя состояния . Пусть будет числом состояний автомата.$R^k_{i,j}$$q_i$$q_j$$\{q_1, …, q_k\}$$n$

Предположим, что вы уже знаете регулярное выражение от до без промежуточного состояния (кроме конечностей) для всех . Затем вы можете догадаться, как добавление другого состояния повлияет на новое регулярное выражение : оно изменяется только при наличии прямых переходов к и может быть выражено так:$R_{i,j}$$q_i$$q_j$$q_k$$i,j$$R'_{i,j}$$q_k$

( является и является .)$R$$R^{k-1}$$R'$$R^k$

пример

Мы будем использовать тот же пример, что и в ответе Рафаэля . Во-первых, вы можете использовать только прямые переходы.

Вот первый шаг (обратите внимание, что сам цикл с меткой преобразовал бы первый в .$a$$ε$$(ε+a)$

На втором шаге мы можем использовать (который для нас переименован в , потому что уже используется для вышеуказанной цели). Посмотрим, как работает .$q_0$$q_1$$R^0$$R^1$

От до : .q 2 R 1 2 , 2 = R 0 2 , 2 + R 0 2 , 1 R 0 1 , 1 ∗ R 0 1 , 2 = ε + b ε ∗ a = ε + b $q_2$$q_2$$R^1_{2,2} = R^0_{2,2} + R^0_{2,1} {R^0_{1,1}}^* R^0_{1,2} = ε + b ε^* a = ε + ba$

Почему это? Это происходит потому, что переход от к с использованием только в качестве промежуточного состояния можно выполнить, оставаясь здесь ( ) или переходя к ( ), повторяя там ( ) и возвращаясь ( ).$q_2$$q_2$$q_1$$ε$$q_1$$a$$ε^*$$b$

Вы можете также вычислить и , и даст вам окончательное выражение, потому что является как начальным, так и конечным. Обратите внимание, что здесь было сделано много упрощений выражений. В противном случае первый из был бы а первый из был бы .R 3 R 3 1 , 1 1 a R 0 ( ∅ + a ) a R 1 ( ( ∅ + a ) + ε ( ε ) ∗ a $R^2$$R^3$$R^3_{1,1}$$1$$a$$R^0$$(∅+a)$$a$$R^1$$((∅+a)+ε(ε)^*a)$

Алгоритм

Инициализация:

for i = 1 to n:
  for j = 1 to n:
    if i == j:
      R[i,j,0] := ε
    else:
      R[i,j,0] := ∅
    for a in Σ:
      if trans(i, a, j):
        R[i,j,0] := R[i,j,0] + a

Транзитивное закрытие:

for k = 1 to n:
  for i = 1 to n:
    for j = 1 to n:
      R[i,j,k] := R[i,j,k-1] + R[i,k,k-1] . star(R[k,k,k-1]) . R(k,j,k-1)

Тогда конечное выражение (предположим, что является начальным состоянием):$q_s$

e := ∅
for i = 1 to n:
  if final(i):
    e := e + R[s,i,n]

Но вы можете себе представить, что он генерирует некрасивые регулярные выражения. Вы действительно можете ожидать такие вещи, как который представляет тот же язык, что и . Обратите внимание, что упрощение регулярного выражения полезно на практике.a $(∅)^*+(a+(∅)^*)(ε)^*(a + ∅)$$aa$