Изменения

Время работы модифицированного {{Лемма|about = 1|id = Лемма1|statement =Количество классов, созданных во время выполнения алгоритма оценивается как , не превышает <tex>O(2 |\SigmaQ| \cdot n\log{n})- 1</tex>|proof =Представим дерево, где которое соответствует операциям разделения классов на подклассы. Корнем этого дерева является все множество состояний <tex> n Q</tex> {{---}} количество состояний ДКА. Листьями являются классы эквивалентности, а <tex> \Sigma </tex>оставшиеся после работы алгоритма. Так как дерево бинарное {{---}} алфавит. В данном случае при последующем разбиении в очередь будет добавлен каждый класс <tex>S_1</tex>может породить лишь два новых, причем а количество листьев не может быть больше <tex>|S| \ge 2|S_1Q|</tex>. Каждый переход в автомате будет просмотрен , то количество узлов этого дерева не более, чем может быть больше <tex>O(\log{n})</tex> раз, ребер всего <tex>O(2 |\SigmaQ| \cdot n)- 1</tex>, отсюда указанная оценкачто доказывает утверждение леммы.}}