Kontextfreie Gramatiken nennt man auch Phrasenstruktur- (PSG), Konstituentenstruktur oder Typ-2-Grammatiken.

Inhalt

Aufbau

Eine PSG ist ein Quadrupel (N,T, R,S) bestehend aus

• N = endliche Menge von nichtterminalen Symbolen

  • = den syntaktischen Kategorien -> Sowohl grammatikalisch als auch lexalisch

  • K = Menge von terminalen Symbolen
    • = dem Lexikon oder Aphalbet

  • R = Menge von Erzeugungsregeln der Form X

            $\rightarrow $
       * S = ausgezeichnetes Startsymbol 

    Y1 . . . Yn, wobei der Pfeil bedeutet: darf ersetzt werden durch .

terminale und nichtterminale Symbole

Ein Symbol einer PSG heißt terminal wenn

• es in Ersetzungsregeln nur rechts vom Pfeil vorkommt,
  • sonst nichtterminal
    • d.h. Terminale können nicht weiter durch ersetzt andere Nichtterminale ersetzt werden
      • d.h. Nichtterminale stehen für weitere Terminale oder Nichterminale
        • also wie eine Art Zusammenfassung von Elementen
          • Beispiel:

            • es sei A -> hallo ein Nichtterminal somit ist hallo ein Terminal

              • ( '-> ' bedeutet "wird ersetzt durch")

              andereseits könnte aber auch

              • B-> A_du

              • wegen A -> hallo folgt

                • B -> hallo_du

    • Beispiel:
      • eine Menge terminaler Symbole:

        • T = {die, manche, kinder, stanken, und, oder, mädchen, verdrossen}
          

      • Beispiel:
        • eine Menge nichtterminaler Symbole:
          • N ={kon, n, S, NP, VP, det, av, vi, vt}

Beispiel

Leider noch kein Beispiel vorhanden

PS Grammatik (N,T,S,R)

V_G = {S, NP, VP}
V_L = {kon, n, det, v}
N = V_G

        $\cup $

V_L = {S, NP, VP, n, det, v}BRT = {die, manche, kinder, sahen, und, oder, mädchen, verdrossen, strahlten, dort, hier}
R = { (G1) S

$\rightarrow$

S kon S,BR(G2) S

        $\rightarrow $

NP VP,BR(G3) VP

        $\rightarrow $

v NP,BR(G4) VP

        $\rightarrow $

v,BR(G5) NP

        $\rightarrow $

det n,BR(L1) det

        $\rightarrow $

die, manche,BR(L2) kon

        $\rightarrow $

und, oder, BR(L3) n

        $\rightarrow $

mädchen, kinder,BR (L4) v

        $\rightarrow $

sahen, verdrossen, strahlen, schlugen }

Sätze basteln

Will man einen Satz mit hilfe einer PSG erstellen, so beginnt man mit einem S.

• S

Dieses kann man mit G2 in NP VP transformieren.

• NP VP

Nun kann NP wiederum in det n umgewandelt werden.

• det n VP

VP ist nach G3 = v NP.

• det n v NP

Nach der Umwandlung von NP in det n: det n v det n Setzen wir jezt mit Hilfe der L-Regeln terminale Symbole ein erhalten wir einen korrekten Satz. die Kinder sahen die Mädchen

Sätze analysieren

Will man den Satz Manche Mädchen schlugen die Kinder mithilfe der PSG Abbilden, so ersetzen wir die terminalen Symboledurch nichtterminale.

• det n v det n

Nun ersetzen wir dies wiederum durch Gramatikalische nichtterminale Symbole bis wir bei S angekommen sind.

• NP v NP
  NP VP
  S
  

KategorieInformatik KategorieComputerLinguistik