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

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

Алгоритм

Описание

Обладая обычными процедурами обращения [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] это минимизированный КА.

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

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

Псевдокод

См. также

Литература