В отличие от минимизации DFA , где существуют эффективные методы, позволяющие не только определить размер, но и фактически вычислить наименьший DFA с точки зрения количества состояний, описывающих данный регулярный язык, такого общего нетИзвестен способ определения размера самого маленького НФА.Кроме того, если P = PSPACE , не существует алгоритма полиномиального времени для вычисления минимального NFA для распознавания языка, поскольку следующая проблема решения PSPACE-полная :
Учитывая DFA M , который принимает обычный язык L и целое число k , существует ли NFA с ≤ k утверждает, что принимает L ?
(Jiang & Ravikumar 1993).
Однако существует простая теорема Глейстера и Шаллита, которую можно использовать дляопределить нижние оценки числа состояний минимального NFA:
Пусть L ⊆ Σ * будет регулярным языком и предположим, что он существует n пары P = {( x i , w я ) |1 ≤ i ≤ n } такой, что:
- x i w i ∈ L для 1 ≤ i ≤ n
- x j w i ∉ L для 1 ≤ j , i ≤ n и j ≠ i
Тогда любой NFA, принимающий L , имеет по меньшей мере n состояний.
См .: Ian Glaister and Jeffrey Shallit (1996).« Техника нижней границы для размера недетерминированных конечных автоматов ». Письма обработки информации 59 (2), стр. 75–77.DOI:. 10,1016 / 0020-0190 (96) 00095-6