Warum konvertieren wir die Grammatik in die Chomsky-Normalform? Gibt es einen Vorteil?
Antworten
Zu viele Anzeigen?
jetru
Punkte
1848
ishan3243
Punkte
1710
Mit der Chomsky-Normalform kann ein Algorithmus in polynomialer Zeit entscheiden, ob eine Zeichenkette durch eine Grammatik erzeugt werden kann. Der Algorithmus ist ziemlich raffiniert, wenn man sich mit dynamischer Programmierung auskennt...
Wenn die Länge Ihrer Eingabe (I) n ist, nehmen Sie ein 2d-Array (A) mit den Abmessungen nxn.
A[i,j] bezeichnet alle Symbole in der Grammatik G, die die Teilzeichenkette I(i,j) ableiten können.
Wenn also A[1,n] das Startsymbol (S) enthält, dann bedeutet dies, dass die Zeichenkette I von S abgeleitet werden kann, was wir ja überprüfen wollten.
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 erscheinen. Aber im Grunde passiert Folgendes.
-das Basisbeispiel ist ziemlich klar, denke ich
-Schritt wird die Lösung für einen Teilstring der Länge s aus allen Lösungen mit einer Länge kleiner als s gebildet.
-Angenommen, Sie suchen die Lösung für eine Teilzeichenkette der Länge 5 ( sub ), beginnend bei Index 1. Dann startet man eine Schleife (etwas anderes Teil)....., die prüft, ob es eine Regel (A->BC) gibt, so dass B und C zwei zusammenhängende und disjunkte Teilfolgen von sub ableiten, und wenn ja, fügt man alle solchen A's zu N[1,6] hinzu.
-Wenn Sie das Startsymbol in N[1,n] haben, akzeptieren Sie!
Sanskrati Gupta
Punkte
1
Die Vorteile der Verwendung der Chomsky-Normalform sind:
- Einfachheit des Nachweises Wir haben viele Beweise für kontextfreie Grammatiken, einschließlich der Reduzierbarkeit und der Äquivalenz zu Automaten. Da es sich aber um die einfachere und eingeschränktere Menge von Grammatiken handelt, sind Normalformen hilfreich. Zum Beispiel wird die Greibach-Normalform verwendet, um zu zeigen, dass es für jede CFL (die keine ) eine -transitionsfreie PDA gibt.
2. ermöglicht das Parsing Die PDAs werden zum Parsen von Wörtern mit beliebiger Grammatik verwendet, was unpraktisch ist. Normalformen geben uns mehr Struktur, mit der wir arbeiten können, was zu einfacheren Parsing-Algorithmen führt.
Der CYK-Algorithmus verwendet zum Beispiel die Chomsky-Normalform. Die Greibach-Normalform hingegen ermöglicht ein rekursiv-absteigendes Parsing; auch wenn Backtracking erforderlich sein kann, ist die Raumkomplexität linear.
