2012-01-30 6 views
3

Есть ли какое-то доказательство для этого? Как мы можем знать, что текущий NFA имеет минимальную сумму?Как мы знаем, что NFA имеет минимальное количество состояний?

+0

Ваше сообщение возможно было помечено, из-за отсутствия деталей в вашем вопросе. – octopusgrabbus

ответ

3

В отличие от DFA minimization, где существуют эффективные методы, которые не только определяют размер, но и фактически вычисляют наименьший DFA в терминах количества состояний, которые описывают данный регулярный язык, то такой общий метод не известен для определения размером с наименьший NFA. Кроме того, если P = PSPACE, не алгоритм полиномиального времени не существует, чтобы вычислить минимальную НКУ для распознавания языка, так как следующая задачей является PSPACE-complete:

Учитывая DFA M, который принимает регулярный язык L и целое число k, существует ли NFA с ≤ k состояние принимается L?

(Jiang & Ravikumar 1993).

Существует, однако, простая теорема из Глаистер и Shallit, которые могут быть использованы для определения нижних границ числа состояний минимального НКА:

Пусть L ⊆ Σ * быть регулярный язык и предположим, что существуют п пар P = {(х я, шi) | 1 ≤ яп}, что:

  1. хяшяL для 1 ≤ яп
  2. хJшяL для 1 ≤ J, яп и Jя

Тогда любой NFA принимает L имеет в l восток n состояний.

См. Ian Glaister and Jeffrey Shallit (1996). "A lower bound technique for the size of nondeterministic finite automata". Обработка данных Письма (2), с. 75-77. DOI: 10.1016/0020-0190(96)00095-6.

+1

ОК, поэтому полиномиальное время или пространство невозможно. Что делать, если нас не касается производительности. Конечно, есть исчерпывающий алгоритм, нет? PSPACE-complete не означает неразрешимый, не так ли? – Brent

+0

@Brent: Правильно, PSPACE-complete не означает неразрешимого (в конце концов, [TQBF] (http://en.wikipedia.org/wiki/TQBF) разрешимо рекурсивным алгоритмом). Однако в этом случае утверждение о том, что такой общий метод не известен для определения наименьшего количества NFA, поступает из бумаги Glaister & Shallit. См. Также «[Вычислительная сложность минимизации NFA для конечных и унарных языков] (http://www.hermann-gruber.com/data/lata07-final.pdf)« Герман Грубер и Маркус Хольцер. –

+0

Обратите внимание, что нижняя граница Glaister-Shallit (также известная как метод набора ошибок в сложности вычислений и частный случай более общих нижних границ вычислительной сложности по размерам NFA) не является жесткой. К сожалению, может случиться так, что самый большой возможный набор дураков P имеет n элементов, но минимальные NFA имеют состояния $ 2^O (n) $. –