Здравствуйте эксперты!
Итак я сконструировал DFA из NFA сконструированного из регулярного выражения, встала задача минимизации DFA с использованием алгоритма Hopcroft’а. Мой DFA представлен в виде JSON объекта и выглядит так:
{
0: [{
from: 97,
to: 97,
shift: 1
}],
1: [{
from: 97,
to: 97,
shift: 3
}, {
from: 98,
to: 98,
shift: 2
}],
2: [{
from: 98,
to: 98,
shift: 4
}],
3: [{
from: 97,
to: 97,
shift: 3
}, {
from: 98,
to: 98,
shift: 4
}],
4: [{
from: 98,
to: 98,
shift: 4
}]
}
Ключами объекта соответственно являются номера стэйтов (0 — стартовый стэйт), каждый стэйт представляет собой массив объектов каждый из которых представляет собой интервал символов (from, to) и тот стэйт на который необходимо совершить переход (shift).
Хотелось бы получить минимальный DFA из представленного. Одним из методов является конструирование таблицы пар стэйтов по алгоритму Hopcroft’а затем проход по таблице и выявление идентичных стэйтов (таких которые идут на одни и те же стэйты при одних и тех же символах). Я не до конца понял как происходит минимизация в алгоритме Hopcroft’а, но то что я понял заставляет меня думать о том что это можно сделать проще.
Итак мой алгоритм минимизации заключается в следующем:
1. Для каждого стэйта (обозначенного как 0, 1, 2, 3, 4 в моем примере) необходимо получить уникальный хэш его идентифицирующий (к примеру для стэйта 0 это будет: from=97,to=97,shift=1, для стэйта 1 это будет: from=97,to=97,shift=3&from=98,to=98,shift=2 и так далее…)
2. Сравним полученные хэши и если мы найдем два одинаковых, значит стэйты для которых они были сгенерированы можно склеить вместе (merge). В моем примере, хэш стэйта 2 будет: from=98&shift=4&to=98, и хэш стэйта 4 будет: from=98&shift=4&to=98, они одинаковы, а потому мы можем их склеить вместе получив новый стэйт 5, после этого DFA будет выглядеть так:
{
0: [{
from: 97,
to: 97,
shift: 1
}],
1: [{
from: 97,
to: 97,
shift: 3
}, {
from: 98,
to: 98,
shift: 5
}],
3: [{
from: 97,
to: 97,
shift: 3
}, {
from: 98,
to: 98,
shift: 5
}],
5: [{
from: 98,
to: 98,
shift: 5
}]
}
3. Повторяем шаги 1, 2 до тех пор пока у нас не останется стэйтов с совпадающими хэшами, к примеру следующим шагом станет склеивание стэйтов 1 и 3 с созданием нового стэйта 6, что даст нам следующий DFA:
{
0: [{
from: 97,
to: 97,
shift: 6
}],
6: [{
from: 97,
to: 97,
shift: 6
}, {
from: 98,
to: 98,
shift: 5
}],
5: [{
from: 98,
to: 98,
shift: 5
}]
}
4. Идентичных стэйтов больше нет, значит мы закончили.
Теперь собственно вопрос… является ли данный изобретенный мною велосипед аналогичным по производимому результату (и общему смыслу) алгоритму Hopcroft’а?
