Re: взаимоисключающие regex'ы

From

Alexander Pevzner ()

To

Max Khon ()

Date

2002-08-07T17:48:01Z

Area

RU.UNIX.PROG

From: Alexander Pevzner <pzz@pzz.msk.ru>

Hello, Max Khon!

Sat, 03 Aug 02 10:29:58 +0400 you wrote to Dmitry Astapov:

MK>  DA> Есть алгоритм проверки эквивалентности регулярных языков
MK>  DA> (выражений).  Суть его действительно сводится к проверке того, что
MK>  DA> минимальные детерминированые автоматы, эквивалентные исходным рег.
MK>  DA> выражениям, совпадают с точностью до порядка перечисления
MK>  DA> состояний.

MK> а какая сложность у этого алгоритма?

Ох, ну это уже надо книжку смотреть. Сложность, насколько я понимаю,
будет определяться сложностью построения детерминированного конечного
автомата с минимальным числом состояний по заданному выражению. Я не
помню точных параметров, но они какие-то приемлимые. Во всяком
случае, программа lex делает именно это (строит автомат), и достаточно 
быстро для практически значимых случаев.

--
        Wishes, Alexander Pevzner (pzz@pzz.msk.ru)
--- ifmail v.2.14-tx8.10
 * Origin: Private Node of Alexander Pevzner (2:5020/59.9@fidonet)