Die Bedeutung von Normalformen wie der Chomsky-Normalform für CFGs

12

Ich verstehe, dass kontextfreie Grammatiken verwendet werden können, um kontextfreie Sprachen darzustellen. Es kann Mehrdeutigkeiten geben. Wir haben auch Normalformen wie Chomsky und Greibach Normalform. Ich konnte das nicht verstehen.

Warum sind sie in der Sprachtheorie wichtig? Alle Lehrbücher, auf die ich mich bezog, erzählten von diesen normalen Formen, sagten aber nichts über ihre Wichtigkeit.

user5507
quelle
2
Normale Formen sind nützlich, wenn konstruktive Beweise gegeben werden.
Karolis Juodelė

Antworten:

12

Es gibt mindestens zwei relevante Verwendungen.

  1. Einfachheit von Beweisen
    Es gibt viele Beweise für kontextfreie Grammatiken, einschließlich der Reduzierbarkeit und Äquivalenz zu Automaten. Je einfacher diese sind, desto eingeschränkter ist die Menge der Grammatiken, mit denen Sie umgehen müssen. Daher können dort normale Formulare hilfreich sein.

    Als konkretes Beispiel wird Greibach-Normalform zu zeigen (konstruktiv) verwendet , dass es ein -Elektronenübergang frei PDA für jeden CFL (die nicht enthält ε ).εε

  2. Ermöglicht das Parsen
    Während PDAs zum Parsen von Wörtern mit jeder Grammatik verwendet werden können, ist dies häufig unpraktisch. Normale Formen können uns mehr Struktur zum Arbeiten geben, was zu einfacheren Analysealgorithmen führt.

    Als konkretes Beispiel verwendet der CYK-Algorithmus die Chomsky-Normalform. Die Greibach-Normalform hingegen ermöglicht das Parsen nach rekursivem Abstieg. Auch wenn möglicherweise eine Rückverfolgung erforderlich ist, ist die Raumkomplexität linear.

Raphael
quelle
5

Die Chomsky-Normalform ermöglicht es einem Polynom-Zeit-Algorithmus, zu entscheiden, ob eine Zeichenkette durch eine Grammatik erzeugt werden kann. Der Algorithmus ist ziemlich clever, wenn Sie sich mit dynamischer Programmierung auskennen ...

ichnEINnn

EIN[ich,j]Gich(ich,j)

EIN[1,n]SS

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.

Ich weiß, dass die Indizes ziemlich verrückt wirken. Aber im Grunde ist hier was passiert.

  • Der Grundfall ist ziemlich klar, denke ich.

  • ss

  • 5sub1EIN->BCBCEINN[1,6]

  • N[1,n]

  • ishan3243
    quelle
    3
    Dies ist der CYK-Algorithmus, den a) Sie als solchen bezeichnen sollten und b) in meiner Antwort erwähnt wurde. Beachten Sie, dass die polynomielle Laufzeit nur deshalb beeindruckend ist, weil der Algorithmus über alle CFGs hinweg einheitlich ist, dh allgemein.
    Raphael
    @ Raphael ok .... ich wusste nicht den Namen :)
    ishan3243
    4

    ϵ

    Dominik D. Freydenberger
    quelle