5

なぜ文法をチョムスキー標準形に変換するのですか? 利点はありますか？

4

4 に答える 4

3

1 つには、Chomsky Normal Form 文法で CYK アルゴリズムを使用できます。

于 2011-02-03T08:25:37.287 に答える
2

チョムスキー正規形により、多項式時間アルゴリズムは、文法によって文字列を生成できるかどうかを判断できます。動的計画法を知っていれば、アルゴリズムはかなり洗練されています...

入力の長さ (I) が n の場合、dim nxn の 2 次元配列 (A) を取得します。

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.

インデックスがかなり狂っているように見えることは知っています。しかし、基本的にここで何が起こっているかです。

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

- 帰納的ステップでは、長さが s 未満のすべての解から、長さ s の部分文字列の解を作成します。

-たとえば、インデックス 1 から始まる長さ 5 の部分文字列 ( ) の解を見つけているとsubします。次に、ループ (他の部分) を開始します。これは、B とC は、sub の 2 つの連続したばらばらの部分文字列を導出し、そうであれば、そのようなすべての A を N[1,6] に追加します。

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

于 2013-11-29T19:26:05.813 に答える
1

たとえば、CNF (またはその派生ツリー) の文法は、文脈自由言語のポンピング補題を証明するために使用されます。

于 2011-02-03T09:37:04.263 に答える
0

チョムスキー正規形を使用する利点は次のとおりです。

  1. 証明の単純さ 還元可能性やオートマトンとの等価性を含む、文脈自由文法の多くの証明があります。しかし、これらはより単純で、より制限された一連の文法を扱う必要があります。したがって、通常の形式が役に立ちます。たとえば、Greibach 正規形は、すべての CFL (ε を含まない) に対して ε 遷移のない PDA があることを示すために使用されます。

2.構文解析が可能 PDA は、不便な文法で単語を構文解析するために使用されます。正規形を使用すると、より多くの構造を扱うことができるため、解析アルゴリズムがより簡単になります。

たとえば、CYK アルゴリズムはチョムスキー正規形を使用します。一方、Greibach の正規形では、再帰降下の構文解析が可能です。バックトラッキングが必要な場合でも、スペースの複雑さは直線的です。

于 2021-01-03T15:37:56.613 に答える