DFA minimization

Question

У меня вопрос о минимизации DFA. Поэтому я использовал очень хорошо известные методы для преобразования регулярного выражения в NFA, а затем построил из него DFA, используя алгоритм goto/clos. Теперь вопрос в том, как свести его к минимуму? Я смотрел лекции об этом здесь: http://www.youtube.com/watch?v=T9Z66NF5YRk, и я до сих пор не могу понять. Что такое минимизация DFA? Является ли это просто слиянием ИДЕНТИКАЛЬНЫХ состояний (состояний, которые поступают в одни и те же состояния на одни и те же символы) или что-то другое?

Итак, я начал со следующей грамматикой:

%digit = '0'..'9' 
%letter = 'a'..'z' | 'A'..'Z' 
%exponent = ("e" | "E") ("+" | "-")? digit+ 

T_INT = digit+ 
T_FLOAT = T_INT exponent 
T_IDENTIFIER = (letter | "$" | "_") (letter | "$" | "_" | digit)* 

и в конечном итоге со следующим DFA (представлено в виде JSON):

{ 
    "START": [{ 
     "type": "range", 
     "from": 36, 
     "to": 36, 
     "shift": "1" 
    }, { 
     "type": "range", 
     "from": 48, 
     "to": 57, 
     "shift": "2" 
    }, { 
     "type": "range", 
     "from": 65, 
     "to": 90, 
     "shift": "1" 
    }, { 
     "type": "range", 
     "from": 95, 
     "to": 95, 
     "shift": "1" 
    }, { 
     "type": "range", 
     "from": 97, 
     "to": 122, 
     "shift": "1" 
    }], 
    "1": [{ 
     "type": "range", 
     "from": 36, 
     "to": 36, 
     "shift": "1" 
    }, { 
     "type": "range", 
     "from": 48, 
     "to": 57, 
     "shift": "1" 
    }, { 
     "type": "range", 
     "from": 65, 
     "to": 90, 
     "shift": "1" 
    }, { 
     "type": "range", 
     "from": 95, 
     "to": 95, 
     "shift": "1" 
    }, { 
     "type": "range", 
     "from": 97, 
     "to": 122, 
     "shift": "1" 
    }, { 
     "shift": ["t_identifier"] 
    }], 
    "2": [{ 
     "type": "range", 
     "from": 48, 
     "to": 57, 
     "shift": "2" 
    }, { 
     "type": "range", 
     "from": 69, 
     "to": 69, 
     "shift": "3" 
    }, { 
     "type": "range", 
     "from": 101, 
     "to": 101, 
     "shift": "3" 
    }, { 
     "shift": ["t_int"] 
    }], 
    "3": [{ 
     "type": "range", 
     "from": 43, 
     "to": 43, 
     "shift": "5" 
    }, { 
     "type": "range", 
     "from": 45, 
     "to": 45, 
     "shift": "5" 
    }, { 
     "type": "range", 
     "from": 48, 
     "to": 57, 
     "shift": "4" 
    }], 
    "4": [{ 
     "type": "range", 
     "from": 48, 
     "to": 57, 
     "shift": "4" 
    }, { 
     "shift": ["t_float"] 
    }], 
    "5": [{ 
     "type": "range", 
     "from": 48, 
     "to": 57, 
     "shift": "4" 
    }] 
} 

Так как же я минимизировать это?

UPDATE:

Хорошо, так вот мой алгоритм. Учитывая следующие DFA:

{ 
    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 
    }] 
} 

Это то, что я делаю, чтобы свести его к минимуму:

1. Для каждого состояния (пронумерованных как 0, 1, 2, 3, 4 в моем примере) получить уникальный хэш идентифицирует такое состояние (например, для состояния 0 это будет: от = 97, до = 97, shift = 1, для состояния 1 это будет: от = 97, до = 97, shift = 3 & от = 98, до = 98, shift = 2 и т. д.)

2. Сравните полученные хэши, и если мы найдем два одинаковых, то слейте их. В моем примере хеш состояния2 будет: от = 98 & shift = 4 & to = 98, а состояние hash будет: от = 98 & shift = 4 & to = 98, они одинаковы, поэтому мы можем объединить их в новый state5, после чего 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 и 3) преобразует 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. Нет более идентичных состояний, это означает, что мы закончили.

ВТОРАЯ UPDATE:

Итак, учитывая следующее регулярное выражение: 'а' ('се') * ('d' | 'ха' | 'AFE') + | 'b' ('ce') * ('d' | 'aa' | 'AFe') + 'ce' + У меня есть следующее DFA (START -> start state, ["accept"] -> so to например, переход в принимающее состояние):

{ 
    "START": [{ 
     "type": "range", 
     "from": 98, 
     "to": 98, 
     "shift": "1.2" 
    }, { 
     "type": "range", 
     "from": 97, 
     "to": 97, 
     "shift": "17.18" 
    }], 
    "1.2": [{ 
     "type": "range", 
     "from": 120, 
     "to": 120, 
     "shift": "10" 
    }, { 
     "type": "range", 
     "from": 100, 
     "to": 100, 
     "shift": "6.7" 
    }, { 
     "type": "range", 
     "from": 65, 
     "to": 65, 
     "shift": "8" 
    }, { 
     "type": "range", 
     "from": 99, 
     "to": 99, 
     "shift": "4" 
    }], 
    "10": [{ 
     "type": "range", 
     "from": 97, 
     "to": 97, 
     "shift": "6.7" 
    }], 
    "6.7": [{ 
     "type": "range", 
     "from": 99, 
     "to": 99, 
     "shift": "15" 
    }, { 
     "type": "range", 
     "from": 120, 
     "to": 120, 
     "shift": "13" 
    }, { 
     "type": "range", 
     "from": 100, 
     "to": 100, 
     "shift": "6.7" 
    }, { 
     "type": "range", 
     "from": 65, 
     "to": 65, 
     "shift": "11" 
    }], 
    "15": [{ 
     "type": "range", 
     "from": 101, 
     "to": 101, 
     "shift": "14.accept" 
    }], 
    "14.accept": [{ 
     "type": "range", 
     "from": 99, 
     "to": 99, 
     "shift": "16" 
    }, { 
     "shift": ["accept"] 
    }], 
    "16": [{ 
     "type": "range", 
     "from": 101, 
     "to": 101, 
     "shift": "14.accept" 
    }], 
    "13": [{ 
     "type": "range", 
     "from": 97, 
     "to": 97, 
     "shift": "6.7" 
    }], 
    "11": [{ 
     "type": "range", 
     "from": 70, 
     "to": 70, 
     "shift": "12" 
    }], 
    "12": [{ 
     "type": "range", 
     "from": 101, 
     "to": 101, 
     "shift": "6.7" 
    }], 
    "8": [{ 
     "type": "range", 
     "from": 70, 
     "to": 70, 
     "shift": "9" 
    }], 
    "9": [{ 
     "type": "range", 
     "from": 101, 
     "to": 101, 
     "shift": "6.7" 
    }], 
    "4": [{ 
     "type": "range", 
     "from": 101, 
     "to": 101, 
     "shift": "2.3" 
    }], 
    "2.3": [{ 
     "type": "range", 
     "from": 120, 
     "to": 120, 
     "shift": "10" 
    }, { 
     "type": "range", 
     "from": 100, 
     "to": 100, 
     "shift": "6.7" 
    }, { 
     "type": "range", 
     "from": 65, 
     "to": 65, 
     "shift": "8" 
    }, { 
     "type": "range", 
     "from": 99, 
     "to": 99, 
     "shift": "5" 
    }], 
    "5": [{ 
     "type": "range", 
     "from": 101, 
     "to": 101, 
     "shift": "2.3" 
    }], 
    "17.18": [{ 
     "type": "range", 
     "from": 120, 
     "to": 120, 
     "shift": "25" 
    }, { 
     "type": "range", 
     "from": 100, 
     "to": 100, 
     "shift": "22.accept" 
    }, { 
     "type": "range", 
     "from": 65, 
     "to": 65, 
     "shift": "23" 
    }, { 
     "type": "range", 
     "from": 99, 
     "to": 99, 
     "shift": "20" 
    }], 
    "25": [{ 
     "type": "range", 
     "from": 97, 
     "to": 97, 
     "shift": "22.accept" 
    }], 
    "22.accept": [{ 
     "type": "range", 
     "from": 120, 
     "to": 120, 
     "shift": "28" 
    }, { 
     "type": "range", 
     "from": 100, 
     "to": 100, 
     "shift": "22.accept" 
    }, { 
     "type": "range", 
     "from": 65, 
     "to": 65, 
     "shift": "26" 
    }, { 
     "shift": ["accept"] 
    }], 
    "28": [{ 
     "type": "range", 
     "from": 97, 
     "to": 97, 
     "shift": "22.accept" 
    }], 
    "26": [{ 
     "type": "range", 
     "from": 70, 
     "to": 70, 
     "shift": "27" 
    }], 
    "27": [{ 
     "type": "range", 
     "from": 101, 
     "to": 101, 
     "shift": "22.accept" 
    }], 
    "23": [{ 
     "type": "range", 
     "from": 70, 
     "to": 70, 
     "shift": "24" 
    }], 
    "24": [{ 
     "type": "range", 
     "from": 101, 
     "to": 101, 
     "shift": "22.accept" 
    }], 
    "20": [{ 
     "type": "range", 
     "from": 101, 
     "to": 101, 
     "shift": "18.19" 
    }], 
    "18.19": [{ 
     "type": "range", 
     "from": 120, 
     "to": 120, 
     "shift": "25" 
    }, { 
     "type": "range", 
     "from": 100, 
     "to": 100, 
     "shift": "22.accept" 
    }, { 
     "type": "range", 
     "from": 65, 
     "to": 65, 
     "shift": "23" 
    }, { 
     "type": "range", 
     "from": 99, 
     "to": 99, 
     "shift": "21" 
    }], 
    "21": [{ 
     "type": "range", 
     "from": 101, 
     "to": 101, 
     "shift": "18.19" 
    }] 
} 

История такая же, как ее минимизировать?Если я следую классическому алгоритму Хопкрофта со всей этой конструкцией таблицы, определяя неразличимые состояния, объединяя их вместе и так далее, тогда я собираюсь получить DFA, который содержит 15 состояний (используйте этот инструмент: http://regexvisualizer.apphb.com/ с этим регулярным выражением a (ce) (d | xa | AFe) + | b (ce) (d | xa | AFe) + ce +, чтобы проверить это). Вот как DFA выглядит после минификация с алгоритмом Hopcroft по:

Алгоритм, который я придумал, после того, как «переосмысление» алгоритма Hopcroft, в строит DFA, который меньше, чем тот, который вы можете увидеть выше (извините для качества изображения, мне пришлось перерисовывать его шаг за шагом, чтобы понять, почему это меньше):

А вот как это работает, решение о «государственной эквивалентности» на основе результата хэш функция, которой задано состояние (например, «СТАРТ») b uilds короткие строки, которые могут быть построены из DFA, если мы начнем с этого состояния. Учитывая DFA выше и состояние START, мы можем построить следующие строки: 98-> 120, 98-> 100, 98-> 65, 98-> 99, 97-> 120, 97-> 100, 97-> 65 , 97-> 99, поэтому пусть это будет результат хэш-функции для состояния START. Если мы запустим эту функцию для каждого состояния в DFA, мы увидим, что для некоторых состояний эта функция дает нам одинаковые результаты («1,2», «6,7», «2,3» и «10», «13» и «15», , «16» и «11», «8», «26», «23» и «12», «9», «4», «5», «20», «21» AND «17.18», 18.19 "и" 25 "," 28 "и" 27 "," 24 "), поэтому все, что нам нужно сделать, это объединить эти состояния вместе.

Я вижу, что я где-то не прав, но не понимаю, что случилось с минимизированным DFA, созданным моим алгоритмом?

Answer 1

Ваш предложенный алгоритм не делает полной минимизации, поскольку он не обнаруживает сложные структуры, которые ведут себя одинаково. Чтобы понять этот взгляд на этом DFA (нарисованный JFLAP):

Минимизация сочетались бы q1 и q2, но наметившееся алгоритм не удается.

В отличие от этого, алгоритм Hopcroft был бы первоначально разделить так:

{q0, q1, q2}, {q3} 

затем разделить первый сет, потому что q0 не имеет переход к q3:

{q0}, {q1, q2}, {q3} 

и не расколоть далее, поскольку q1 и q2 ведут себя одинаково.

Answer 2

Позвольте вашему оригинальному DFA назвать M1. Проще говоря, построение минимизированного DFA (назовем его M2) ​​подразумевает преобразование его в DFA, который содержит минимальное количество состояний. Таким образом, число состояний в M2 будет меньше числа состояний в M1. Здесь важно отметить, что M1 и M2 должны быть эквивалентными, а это значит, что они должны определять САМЫЙ обычный язык. Построение свернутого DFA не только включает в себя ищет одинаковые состояния, но также следующее:

1. Удаления «недостижимы» гласит:
   Это включает в себя удалением состояний, которые не достижимы из начального состояния DFA, для любой входной строки.

2. Удаление состояний «мертвых» или «ловушек»:
   Это связано с удалением непринятых состояний, которые заканчиваются на себе. Они также называются состояниями TRAP.

3. Удаление состояний «Неразличимые»:
   Это включает в себя удаление состояний, которые нельзя отличить друг от друга для любой входной строки.

Есть также некоторые популярные алгоритмы, используемые для минимизации DFA:

• Moore's algorithm

• Brzozowski's algorithm

• Hopcroft's algorithm

Возможно, стоит пройти через эти алгоритмы!

Answer 3

Учитывая, что у вас есть код для определения NFA для DFA, самым простым решением для минимизации является алгоритм Бржозовского. Вам нужно будет реализовать функцию для изменения NFA, но это довольно просто. (обратный переходы, поменяем местами начала и принимать состояния)

После того, как у вас есть determinize и функцию реверс, минимизация Brzozowski реализуется как:

minimize(nfa) = determinize(reverse(determinize(reverse(nfa)))) 

ИМХО, это очень элегантное решение