チョムスキー正規形

Question

なぜチョムスキー正規形に変換するのですか？利点はありますか？

Answer 1

文法を使用することができ、CNF（というかその派生ツリー）における文法は文脈自由言語の反復補題を証明するために使用されます。

Answer 2

一つには、あなたはチョムスキー標準形にcyk法を例えば

Answer 3

チョムスキー正規形では、多項式時間アルゴリズムを使用して、文字列を文法で生成できるかどうかを判断できます。 動的プログラミングを知っていればアルゴリズムはかなり滑らかです...

入力の長さがnの場合、dim nxnの2次元配列（A）を取ることになります。 [i、j]は、サブストリングI（i、j）を導出することができる文法G中のすべての記号を意味する。

最後に、A [1、n]に開始記号（S）が含まれていれば、文字列IはSで導出できることを意味します。

def decide (string s,grammar G): 
    //base case 
    for i=1 to n: 
     N[i,i]=I[i] //as the substring of length one can be generated by only a 
         terminal. 
    //end base case 

    //induction 
    for s=1 to n:  //length of substring 
     for i=1 to n-s-1: //start index of substring 
      for j=i to i+s-1: //something else 
       if there exists a rule A->BC such that B belongs to N[i,j] and C 
       belongs to N[j+1,i+s-1] then add A to N[i,i+s-1] 
    //endInduction 

    if S belongs to N[1,n] then accept else reject. 

私はインデックスがかなり狂っていることを知っています。しかし基本的にここで何が起きているのですか？

-theベースケースは、私たちは秒未満の長さを持つすべてのソリューションからの長さの部分文字列のためのソリューションを構築する誘導ステップ-in

を考えるかなり明確です。

-sayインデックス1から始まる長さ5の部分文字列（sub）の解を探しています。次に、ルール（A-> BC BとCがsubの2つの連続した部分集合と非共通部分列を導出し、そうであればすべてのAをN [1,6]に加える。

- 最後にN [1、n]に開始記号がある場合は、受け入れます！