Как Вы нормализуете конечный автомат?
Честно, я установил бы репликацию для этого, как будто Вы не блокируете таблицы, Вы вытащите непоследовательные данные из дампа.
, Если дамп занимает время, таблицы, которые были уже выведены, возможно, изменились наряду с некоторой таблицей, которая только собирается быть выведенной.
Так или заблокируйте таблицы или используйте репликацию.
4 ответа
Некоторые неофициальные ответы, чтобы дать вам идеи, для подробных доказательств прочтите хорошую книгу по автоматам, например эту или те, которые упомянуты в других ответах. И я почти уверен, что в Интернете есть материалы, в которых вы сможете найти ответы на все свои вопросы.
- Как найти минимальный детерминированный автомат?
Процедура состоит в том, чтобы исключить повторяющиеся состояния (или объединить эквивалентные состояния). Вы знаете, что состояние и переходы - это ключи для создания строк. По сути, дублированные состояния не способствуют увеличению или уменьшению размера создаваемого языка. Алгоритм начинается с конечных состояний, которые всегда имеют возможность генерировать lamda (пустую строку), и рекурсивно обновляет таблицу, которая указывает на генерирующую способность состояния, и, наконец, объединяет эти состояния без разницы.
- Есть ли способ нормализовать недетерминированные конечные автоматы?
Нормализованный DFA для NFA использует различные наборы состояний NFA в качестве состояний DFA, например, {state0} - (1) -> {state1 , state2}, чтобы удалить недетерминированную часть, нет способа избежать взрывного роста состояний, поскольку DFA должен делать это для представления языка.
- Существует ли алгоритм с линейной временной привязкой для поиска минимального конечного автомата для данной машины ?
Я помню, что лучший вариант - O (NLogN), проделав несколько уловок по повторному использованию информации из какой-то статьи профессора Университета Западного Онтарио, и сомневаюсь, что существуют лучшие. Я считаю, что классический - O (N ^ 2).
- Есть ли способ узнать, эквивалентны ли два конечных автомата?
Да. Получите минимальный, закодируйте состояние по их строке доступа (строка, которая может достичь состояния из начального состояния, это в значительной степени настоящее «имя» состояния) и проверьте карту перехода. Хотя могут быть способы получше, но на bigO большой разницы не будет.
Поскольку все недетерминированные конечные автоматы имеют соответствующий детерминированный конечный автомат, ответы на вопросы 1 и 2 должны быть одинаковыми.
Если вы хотите узнать больше, получите копию "Введение в теорию" of Computing »Майкла Сипсера, который является действительно отличной книгой для изучения этих вещей. Сипсер прекрасно знает, о чем говорит и , как это передать.
Отметьте «Основы проектирования компилятора», начиная с раздела 2.5. Доступно бесплатно онлайн. http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/basics_lulu.pdf
Он охватывает преобразование NFA в DFA и минимизацию DFA. NFA могут экспоненциально расширяться при преобразовании в DFA.
"... любой обычный язык (язык который может быть выражен регулярным выражением, NFA или DFA) имеет уникальный минимальный DFA. Следовательно, мы можем определить эквивалентность регулярных выражений (или NFA или DFA) путем преобразования обоих в минимальные DFA и сравнения результатов ».
- If you are given some deterministic FSM, then you can find an equivalent, minimal one using a quite easy algorithm in O(n2); Hopcroft's algorithm does it in O(n log n). Here you'll find description of both. You can check if A and B are equivalent by minimizing them and checking if they are the same.
- If you are given some nondeterministic FSM, then finding an equivalent, minimal one is PSPACE-complete. In other words, no good algorithm is known and is conjectured that it doesn't exist. Checking equivalence of two nondeterministic automatas is PSPACE-complete too. So, unless there will be a very improbable breakthrough, you should convert the automaton to a deterministic one (this takes much time) and then perform checks.
- You can transform a nondeterministic FSM to a deterministic one with exponential number of states. This is unavoidable. Exercise (not hard!): the language consisting of words in which the n-th letter from the end is "a" can be recognized using a nondeterministic FSM with n states, and it cannot be recognized using a deterministic FSM with less than 2n states. Exponential bound cannot be broken in general case.