13.4.  Formale Sprachen und Regel-Grammatiken

13.4.1.  Sprache als Menge

Das Alphabet (Sigma), Zeichen und Zeichenketten 

Definition 13.4.1. Ein Alphabet ist eine endliche Menge von Zeichen (atomare Symbole). Es wird mit Σ (Sigma) notiert.

Definition 13.4.2. Eine Zeichenkette (Wort, string) von n Zeichen aus Σ ist eine endliche Folge der Länge n über Σ.

Die leere Zeichenkette (leeres Wort) ist die Folge von 0 Zeichen. Sie wird mit ϵ (Epsilon) notiert und hat die Länge 0.

Hinweis zur Notation

Eine Zeichenkette wird typischerweise durch Nebeneinanderschreiben (Juxtaposition) der Zeichen von links nach rechts notiert.

Sei Σ = {a,b}, dann sind etwa ϵ, a, bb oder ababbba Wörter über Σ. Eine explizitere Notation für bb ist b,bbzw.{〈1,b,2,b〉}.

Stern von Sigma und formale Sprachen 

Definition 13.4.3. Der Stern von Sigma ist die Menge aller Wörter über einem Alphabet Σ. Der Stern wird als Postfix-Operator Σ (sprich «Sigma Stern») notiert.

Definition 13.4.4. Eine formale Sprache L über Σ ist eine Teilmenge des Sterns von Sigma.

     ∗
L ⊆ Σ

Beispiel 13.4.5. Sei Σ = {a}, dann ist Σ = {ϵ,a,aa,aaa,}. Die Mengen L1 = {ϵ,a} oder L2 = {aa,aaaa,aaaaaa} sind formale Sprachen, da sie (echte) Teilmengen von Σ sind.

Leere Sprachen vs. leere Zeichenkette 

Hinweise

Fragen

13.4.2.  Konkatenation

Konkatenation von Zeichenketten 

Definition 13.4.6. Die Konkatenation von Zeichenketten ist eine zweistellige Funktion, welche ihre Argumente zu einem Wort verkettet. Für alle u,v Σ:

    ∗    ∗     ∗
∙ : Σ × Σ  → Σ  ,  u∙ v = uv

Was bedeutet uv?

Wenn u : 1..n Σ und v : 1..m Σ Wörter, d.h. endliche Folgen von Zeichen sind, dann ist uv : 1..(m + n) Σ. Wobei für alle Zeichenpositionen i 1..(n + m) gilt:

         {
(uv )(i) =   u(i)     f alls i ≤ n
           v(i− n ) f alls i > n

Potenznotation der Konkatenation 

Eigenschaften der Konkatenation

Die Konkatenation ist assoziativ und hat ϵ als neutrales Element . Für alle u,v,w Σ:

u ∙(v ∙w ) = (u ∙v) ∙w,  ϵ∙ u = u,  u∙ ϵ = u

Definition 13.4.7. Die n-fache Konkatenation einer Zeichenkette w mit sich selbst in der Potenznotation sei rekursiv definiert. Für n 1,n :

w0  =   ϵ
 n           n−1
w   =   w ∙w

Beispiel 13.4.8 (Potenznotation der Verkettung).
Die Zeichenkette aaabbcccc kann als a3b2c4 notiert werden.

buffalo6 

Beispiel 13.4.9 (Ein syntaktisch korrekter englischer Satz).
“Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo.”

Analyse


pict


13.4.3.  Grammatiken

Chomsky-Hierarchie [HOPCROFT et al. 2002]


pict

Abbildung 13.2: Teilmengenbeziehungen der Sprachklassen von Chomsky




Sprachklasse Typ Beispiel






regulär 3 {an}
kontextfrei 2 {anbn}
kontextsensitiv 1 {anbncn}
allgemein 0



mit n 1

Echte Teilmengen

Für alle Typ–i–Sprachen mit 0 i 2 gilt: Li+1 Li .

Wo befinden sich natürliche Sprachen? [HESS 2005, 138ff.]

Mindestens Typ 2: NPnVPn (central embedding)

      -----------------------------------------------  
     |          ----------------------------         |  
     |         |            --------        |        |  
     |         |           |        |       |        |  
The man whose wife whose child is angry is sad is surprised

Mindestens Typ 1 nach [SHIEBER 1985, KALLMEYER 2005]: NPiNPjViVj (cross serial construction)

                              ------------------  
                             |                  |  
                        ------------------      |  
                       |     |            |     |  
                --------------------      |     |  
               |       |     |      |     |     |  
mer wänd   d’Chind am Hans s’Huus  laa  hälfe aaschtriiche

Komplexität, Grammatikalität, Akzeptanz von Sprache 
Es darf daher getrost, was auch von allen, deren Sinne, weil sie unter Sternen, die, wie der Dichter sagt, zu dörren, statt zu leuchten, geschaffen sind, geboren sind, vertrocknet sind, behauptet wird, enthauptet werden, dass hier einem sozumaßen und im Sinne der Zeit, dieselbe im Negativen als Hydra betrachtet, hydratherapeutischen Moment ersten Ranges, immer angesichts dessen, dass, wie oben, keine mit Rosenfingern den springenden Punkt ihrer schlechthin unvoreingenommenen Hoffnung auf eine, sagen wir, schwansinnige oder wesenzielle Erweiterung des natürlichen Stoffeides zusamt mit der Freiheit des Individuums vor dem Gesetz ihrer Volksseele zu verraten den Mut, was sage ich, die Verruchtheit haben wird, einem Moment, wie ihm in Handel, Wandel, Kunst und Wissenschaft allüberall dieselbe Erscheinung, dieselbe Tendenz den Arm bietet, und welches bei allem, ja vielleicht eben trotz allem, als ein mehr oder minder undulationsfähiger Ausdruck einer ganz bestimmten und im weitesten Verfolge excösen Weltauffasseraumwortkindundkunstanschauung kaum mehr zu unterschlagen versucht werden zu wollen vermag - gegenübergestanden und beigewohnt werden zu dürfen gelten lassen zu müssen sein möchte.

Christian Morgenstern, Vorrede zu Galgenliedern

Regel-Grammatiken 

Kontextfreie Grammatiken 

Beispiel 13.4.10 (Kontextfreie Grammatik).

Beispiel-Evaluation
Siehe Abb. 13.3 auf Seite 530.


PIC PIC PIC PIC PIC PIC PIC PIC PIC

Abbildung 13.3: Beispiel für Linksderivation und Parsebaumkonstruktion

Formales Ableiten von Sätzen 

Definition 13.4.11 (Direkte Ableitungsrelation). Die direkte Ableitungsrelation ⇒ ⊆ Γ× Γ einer Grammatik ist die Menge aller Paare u,vmit u,v,w,z Γ, für die gilt:

Definition 13.4.12 (Ableitung (derivation)). Eine Ableitung ist ein n-Tupel w1,,wnvon Zeichenketten wi Γ mit (1 i n) , so dass gilt:

Normale Schreibweise für Ableitungen

w1 wn

Beispiel: Ableitung mit kontextfreier Grammatik 


pict






Ableitung u Regel v




u1wu2 w z u1zu2








S ϵ S ϵ S NP VP ϵ NP VP ϵ
NP VP ϵ NP VP NP EN ϵ EN VP
EN VP EN VP ϵ VP V NP EN V NP ϵ
EN V NP EN V NP V EN aß NP
EN aß NP EN aß NP ϵ NP D N EN aß D N ϵ
EN aß D N EN aß D N D den EN aß den N
EN aß den N EN aß den N ϵ N Pudel EN aß den Pudel ϵ
EN aß den Pudel ϵ EN aß den Pudel EN Egon ϵ Egon aß den Pudel
Egon aß den Pudel

Satzformen, Sätze und Sprachen 

Definition 13.4.13 (Ableitungsrelation (derivation relation)). Die Ableitungsrelation ∗
⇒ ist die reflexiv-transitive Hülle von .

Definition 13.4.14 (Satz). Ein Satz a einer Grammatik G = Φ,Σ,R,Sist eine Zeichenkette aus Terminalsymbolen a Σ, so dass gilt:

S +⇒  a

Definition 13.4.15 (Sprache einer Grammatik G). Die Sprache LG einer Grammatik G = Φ,Σ,R,Sist die Menge aller ihrer Sätze a Σ.

             +
LG  = { a | S ⇒ a }

Grammatik-Regeln, Sprachklassen und Automaten 
Die verschiedenen Grammatiktypen unterscheiden sich hinsichtlich der Bedingungen, die an die Regelmenge R gestellt werden. Es seien A,B Φ,w Σ und α,β,γ Σ).





Sprachklasse
Form der Grammatikregeln
Automatentyp








Regulär A w Endlicher Automat
(Typ 3) A wB oder A Bw




Kontextfrei A α Kellerautomat
(Typ 2)




Kontext- αAγ αβγ mit βϵ oder
sensitiv S ϵ (dann darf S nicht Linear
(Typ 1) auf einer rechten Seite beschränkter
einer Regel vorkommen) Automat (LBA)




(Typ 0) α β (mit αϵ und α ⁄∈ Σ) Turingmaschine




Die Komplexität der Berechnungen für das Parsen steigt mit jedem Grammatiktyp an.