3

これには何らかの証拠がありますか？現在の NFA が最小額であることをどのように知ることができますか?

4

1 に答える 1

3

DFA 最小化とは対照的に、特定の正規言語を記述する状態の数に関して最小の DFA のサイズを決定するだけでなく、実際に計算するための効率的な方法が存在しますが、そのような一般的な方法は、最小の NFA。さらに、次の決定問題はPSPACE-completeであるため、 P= PSPACEでない限り、言語を認識するための最小の NFA を計算するための多項式時間アルゴリズムは存在しません。

正規言語Lを受け入れるDFA Mと整数kが与えられた場合、 Lを受け入れる状態が ≤ kの NFA はありますか?

(ジャン & ラビクマール 1993)。

ただし、最小 NFA の状態数の下限を決定するために使用できる Glaister と Shallit の単純な定理があります。

L ⊆ Σ *を正規言語とし、n 個のペアP = { ( x i , w i ) | 1 ≤ i ≤ n } で、次のようになります。

  1. x i w i ∈ L for 1 ≤ i ≤ n
  2. x j w i ∉ L for 1 ≤ j , i ≤ n and j ≠ i

次に、 Lを受け入れる任意の NFAには、少なくともn 個の状態があります。

参照: Ian Glaister と Jeffrey Shallit (1996)。「非決定性有限オートマトンのサイズの下限手法」。情報処理レター 59 (2)、pp. 75–77。DOI: 10.1016/0020-0190(96)00095-6 .

于 2012-02-25T21:09:41.027 に答える