Алгоритм Бржозовского для минимизации конечного автомата
1. Введение
Задача минимизации конечного автомата [1] возникает в различных областях, таких, например, как порождение по заданному регулярному выражению соответствующего детерминированного конечного автомата, минимального по числу состояний.Среди прочих алгоритмов минимизации алгоритм от Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами:
- Он элегантен и весьма оригинален.
- Он эффективен (см. раздел “Заключение”).
- Он работает даже с недетерминированными конечными автоматами.
2. Предварительные сведения
Конечным автоматом (КА) будем называть пятёрку:FA = (Q, A, T, S, F), где
- Q это множество состояний,
- A это входной алфавит,
- T это функция переходов, T: Q x A → Q,
- S это множество начальных состояний(подмножество Q),
- F это множество заключительных состояний(подмножество Q).
3. Описание алгоритма
Обладая обычными процедурами обращения (rev) и детерминизации (det) конечного автомата, мы, с помощью идеи Бржозовского, можем немедленно приступить к минимизации заданного автомата. Для этого надо дважды провести его через обе вышеуказанные процедуры:mFA = det(rev(det(rev(FA)))), где
- FA это исходный КА,
- rev это процедура обращения КА,
- det это процедура детерминизации КА,
- mFA это минимизированный КА.
4. Пример работы алгоритма
Исходный НКА:
Рис. 1. Исходный FA
Рис. 2. rev(FA)
Рис. 3. det(rev(FA))
Третий шаг алгоритма (rev(det(rev(FA))):
Рис. 4. rev(det(rev(FA))
Заключительный шаг алгоритма (det(rev(det(rev(FA))))):
Рис. 5. det(rev(det(rev(FA))))
5. Заключение
Самым эффективным алгоритмом минимизации принято считать алгоритм Хопкрофта [5], который, как и прочие традиционные алгоритмы, работает только с ДКА. Его асимптотическое время выполнения зависит от логарифма исходных данных. С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. На практике же наблюдается парадокс, алгоритм Бржозовского во многих случаях опережает прочие подходы к минимизации, включая и алгоритм Хопкрофта. В работе [6], сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее алгоритма Хопкрофта для автоматов с большим числом переходов.6. Пример реализации
Код на языке Python, приведённый ниже, не претендует на высокое быстродействие.
# fa_min.py
# Демонстрация работы алгоритма Бржозовского
Q = 0
A = 1
T = 2
S = 3
F = 4
# Вывод КА в формате свободно распространяемой утилиты graphviz
def fa_gv(fa, filename):
f = open(filename, 'w')
f.write('digraph fa {\n');
f.write('rankdir=LR;\n');
f.write('node[shape=doublecircle];');
for i in fa[F]:
f.write('"' + str(fa[Q][i]) + '";')
f.write('\nnode[shape=circle];\n');
for t1 in range(0, len(fa[Q])):
for a in range(0, len(fa[A])):
for t2 in fa[T][t1][a]:
f.write('"' + str(fa[Q][t1]) +'"' + '->' + '"' + \
str(fa[Q][t2]) + '"')
f.write('[label="' + str(fa[A][a]) + '"];\n')
f.write('}\n')
f.close()
# Обращение КА
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))))
# Пример работы
fa = [None]*5
fa[Q] = [0, 1, 2, 3]
fa[A] = ['a', 'b']
fa[T] = [[[1, 2], [2]], [[2], [3]], [[1, 2], [3]], [[], []]]
fa[S] = [0]
fa[F] = [3]
fa_gv(fa_min(fa), 'fa_min.gv')
Список литературы
| [1] | Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений. Второе издание. Издательство “Вильямс”. |
| [2] | Brzozowski (J.A.). - Canonical regular expressions and minimal state graphs for definite events, “Mathematical theory of automata”, New York, 1962. |
| [3] | Bruce W. Watson. A taxonomy of finite automata minimization. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.8900 |
| [4] | J.-M. Champarnaud, A. Khorsi, T. Paranthoen. Split and join for minimizing: Brzozowski's algorithm. http://jmc.feydakins.org/pdf/c09psc02.pdf |
| [5] | Hopcroft, John E (1971). An n log n algorithm for minimizing states in a finite automaton. ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf |
| [6] | Deian Tabakov, Moshe Y. Vardi. Experimental evaluation of classical automata constructions http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.59.8276 |