Алгоритм Бржозовского — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
(Литература)
Строка 75: Строка 75:
  
 
==Литература==
 
==Литература==
 +
* [http://sovietov.com/txt/minfa/minfa.html Алгоритм Бржозовского для минимизации конечного автомата]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Версия 06:01, 18 ноября 2014

Эта статья находится в разработке!
Задача:
Пусть дан автомат [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] это минимизированный КА.

Корректность

Пример работы

Псевдокод

  • Обращение КА
   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
  • Детерминизация КА
   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
  • Алгоритм Бржозовского
   def fa_min(fa):
       return fa_det(fa_rev(fa_det(fa_rev(fa))))

См. также

Литература