Алгоритм Бржозовского
Эта статья находится в разработке!
| Задача: |
| Пусть дан автомат . Требуется построить автомат с наименьшим количеством состояний, распознающий тот же язык, что и . |
Алгоритм
Описание
Алгоритм минимизации конечных автоматов Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами:
- Он элегантен и весьма оригинален.
- Он эффективен.
- Он работает даже с недетерминированными конечными автоматами.
Обладая обычными процедурами обращения и детерминизации конечного автомата, мы, с помощью идеи Бржозовского, можем немедленно приступить к минимизации заданного автомата. Для этого надо дважды провести его через обе вышеуказанные процедуры:
, где
- это исходный КА,
- это процедура обращения КА,
- это процедура детерминизации КА,
- это минимизированный КА.
Корректность
Пример работы
Псевдокод
- Обращение КА
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))))
