[ Zurück ] [ Zurück (Seitenende) ] [ Seitenende ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]
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 Σ.
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,b〉 bzw.{〈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.
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
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 ∈ Σ∗:
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:
Potenznotation der Konkatenation
Eigenschaften der Konkatenation
Die Konkatenation ist assoziativ und hat ϵ als neutrales Element . Für alle u,v,w ∈ Σ∗:
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 ∈ ℕ:
Beispiel 13.4.8 (Potenznotation der Verkettung).
Die Zeichenkette aaabbcccc kann als a3b2c4 notiert werden.
Beispiel 13.4.9 (Ein syntaktisch korrekter englischer Satz).
“Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo.”
Analyse
|
Chomsky-Hierarchie [HOPCROFT et al. 2002]
Sprachklasse | Typ | Beispiel |
regulär | 3 | {an} |
kontextfrei | 2 | {anbn} |
kontextsensitiv | 1 | {anbncn} |
allgemein | 0 | |
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)
Mindestens Typ 1 nach [SHIEBER 1985, KALLMEYER 2005]: NPiNPjViVj (cross serial construction)
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
Beispiel 13.4.10 (Kontextfreie Grammatik).
Beispiel-Evaluation
Siehe Abb. 13.3 auf Seite 530.
Definition 13.4.11 (Direkte Ableitungsrelation). Die direkte Ableitungsrelation ⇒ ⊆ Γ∗× Γ∗ einer Grammatik ist die Menge aller Paare 〈u,v〉 mit u,v,w,z ∈ Γ∗, für die gilt:
Definition 13.4.12 (Ableitung (derivation)). Eine Ableitung ist ein n-Tupel 〈w1,…,wn〉 von Zeichenketten wi ∈ Γ∗ mit (1 ≤ i ≤ n) , so dass gilt:
Normale Schreibweise für Ableitungen
Beispiel: Ableitung mit kontextfreier Grammatik
|
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 → aß | 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,S〉 ist eine Zeichenkette aus Terminalsymbolen a ∈ Σ∗, so dass gilt:
Definition 13.4.15 (Sprache einer Grammatik G). Die Sprache LG einer Grammatik G = 〈Φ,Σ,R,S〉 ist die Menge aller ihrer Sätze 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.
[ Zurück ] [ Zurück (Seitenende) ] [ Seitenbeginn ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]