チョムスキーノーマルフォーム

Question

なぜ私たちは文法をチョムスキーの通常の形に変換するのですか？利点はありますか？

Answer 1

たとえば、CNF（またはむしろその派生ツリー）の文法は、コンテキストのない言語の補足を証明するために使用されます。

Answer 2

一つには、Chomsky Normal Form GrammarsでCykアルゴリズムを使用できます

Answer 3

Chomsky Normal Formを使用すると、多項式時間アルゴリズムが文字列によって文字列を生成できるかどうかを決定できます。動的プログラミングを知っている場合、アルゴリズムはかなり滑らかです...

入力（i）の長さがnの場合、DIM NXNの2D配列（a）を使用します。

a [i、j]は、サブストリングI（i、j）を導出できる文法Gのすべての記号を示します。

したがって、最後に、[1、n]にスタート記号が含まれている場合、それは私がチェックしたいものである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.

インデックスはかなりクレイジーに見えることを知っています。しかし、基本的にここに何が起こっているのかがあります。

- 基本ケースはかなり明確だと思います

- 誘導ステップでは、s未満の長さのすべてのソリューションからの長さのサブストリングのソリューションを構築します。

- たとえば、5つのサブストリングのソリューションを見つけています（sub）インデックス1から始めてから、ループ（何か他の部分）を開始します.....これは、BとCが2つの連続したばらつきのサブストリングを導き出すようにルール（a-> bc）があるかどうかをチェックします。そのようなAをすべてN [1,6]に追加します。

- まず、n [1、n]にスタート記号がある場合、受け入れます！