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

Эта статья находится в разработке!

Задача:

Пусть дан автомат [math]\mathcal{A}[/math]. Требуется построить автомат [math]\mathcal{A}_{min}[/math] с наименьшим количеством состояний, распознающий тот же язык, что и [math]\mathcal{A}[/math].

Алгоритм

Описание

Алгоритм минимизации конечных автоматов Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами:

• Он элегантен и весьма оригинален.
• Он эффективен.
• Он работает даже с недетерминированными конечными автоматами.

Обладая обычными процедурами обращения [math]rev[/math] и детерминизации [math]det[/math] конечного автомата, мы, с помощью идеи Бржозовского, можем немедленно приступить к минимизации заданного автомата. Для этого надо дважды провести его через обе вышеуказанные процедуры:

[math]mFA = det(rev(det(rev(FA))))[/math], где

• [math]FA[/math] это исходный КА,
• [math]rev[/math] это процедура обращения КА,
• [math]det[/math] это процедура детерминизации КА,
• [math]mFA[/math] это минимизированный КА.

Псевдокод

1. Обращение КА

def fa_rev(fa):

   rfa = [list(fa[Q]), list(fa[A]), [], list(fa[F]), list(fa[S])]
   rfa[T] = [[[] for i in range(0, len(fa[A]))] for j in range(0, len(fa[Q]))]
   for t1 in range(0, len(fa[Q])):
       for a in range(0, len(fa[A])):
           for t2 in fa[T][t1][a]:
               rfa[T][t2][a].append(t1)
   return rfa

1. Детерминизация КА

def fa_det(fa):

   def reachable(q, l):
       t = []
       for a in range(0, len(fa[A])):
           ts = set()
           for i in q[l]:
               # объединение множеств (достижимых из l) состояний для символа a
               ts |= set(fa[T][i][a])
           if not ts:
               t.append([])
               continue
           try:
               i = q.index(ts)
           except ValueError:
               i = len(q)
               q.append(ts)
           t.append([i])
       return t
   dfa = [[], list(fa[A]), [], [0], []]
   q = [set(fa[S])]
   while len(dfa[T]) < len(q):
       dfa[T].append(reachable(q, len(dfa[T])))
   dfa[Q] = range(0, len(q))
   dfa[F] = [q.index(i) for i in q if set(fa[F]) & i]
   return dfa

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

def fa_min(fa):

   return fa_det(fa_rev(fa_det(fa_rev(fa))))

См. также

• Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
• Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))