Formale Sprachen und Regel-Grammatiken

[ Zurück ] [ Zurück (Seitenende) ] [ Seitenende ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]

13.4. Formale Sprachen und Regel-Grammatiken

13.4.1. Sprache als Menge

Das Alphabet (Sigma), Zeichen und Zeichenketten

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

Deﬁnition 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 Σ.

Stern von Sigma und formale Sprachen

Deﬁnition 13.4.3. Der Stern von Sigma ist die Menge aller Wörter über einem Alphabet Σ. Der Stern wird als Postﬁx-Operator Σ^∗ (sprich «Sigma Stern») notiert.

Deﬁnition 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 L₁ = {ε,a} oder L₂ = {aa,aaaa,aaaaaa} sind formale Sprachen, da sie (echte) Teilmengen von Σ^∗ sind.

Leere Sprachen vs. leere Zeichenkette

Hinweise

Die leere Sprache ist die leere Menge, notiert als {} oder ∅.
Die Sprache, welche nur die leere Zeichenkette umfasst, wird als {ε} notiert.
Die leere Sprache {} und die Sprache {ε} sind nicht dasselbe.

Fragen

Ist {} eine Sprache über jedem Σ?
Ist die Sprache {ε} Teilmenge jeder nicht-leeren Sprache?
Ist Σ^∗ eine Sprache über Σ?

13.4.2. Konkatenation

Konkatenation von Zeichenketten

Deﬁnition 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

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

Potenznotation der Konkatenation

Deﬁnition 13.4.7. Die n-fache Konkatenation einer Zeichenkette w mit sich selbst in der Potenznotation sei rekursiv deﬁniert. Für n ≥ 1,n ∈ℕ:

w0 = ε wn = w ∙wn −1

Beispiel 13.4.8 (Potenznotation der Verkettung).
Die Zeichenkette aaabbcccc kann als a³b²c⁴ notiert werden.

buﬀalo⁶

Beispiel 13.4.9 (Ein syntaktisch korrekter englischer Satz).
“Buﬀalo buﬀalo Buﬀalo buﬀalo buﬀalo buﬀalo Buﬀalo buﬀalo.”

Analyse

Buﬀalo als Herkunftsadjektiv
buﬀalo als Nomen (Büﬀel)
buﬀalo als Verb (einschüchtern)
Sinn: “Bison from Buﬀalo, New York who are intimidated by other bison in their community also happen to intimidate other bison in their community.”

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	{aⁿ}
kontextfrei	2	{aⁿbⁿ}
kontextsensitiv	1	{aⁿbⁿcⁿ}
allgemein	0

mit n ≥ 1

Echte Teilmengen

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

Wo beﬁnden sich natürliche Sprachen? [HESS 2005, 138ﬀ.]

Mindestens Typ 2: NPⁿVPⁿ (central embedding)

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

Mindestens Typ 1 nach [SHIEBER 1985] (cross serial construction)

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

Regel-Grammatiken

Eine Regel-Grammatik ist ein mächtiges endliches Beschreibungsmittel , um formale Sprachen mit potentiell unendlich vielen Zeichenketten zu speziﬁzieren.
Eine Grammatik G = 〈Φ,Σ,R,S〉 besteht aus:
1. Alphabet Φ: endliche Menge von Nichtterminalsymbolen
2. Alphabet Σ: endliche Menge von Terminalsymbolen mit Φ ∩ Σ = ∅
3. Menge R ⊆ Γ^∗× Γ^∗ von Regeln 〈α,β〉 (mit Gesamtalphabet Γ = Φ ∪ Σ), wobei gilt: α≠ε und α ⁄∈ Σ^∗
4. Startsymbol S ∈ Φ
Diese Deﬁnition einer Grammatik ist die allgemeinste (Typ 0).
Eine Grammatikregel ist ein geordnetes Paar: 〈α,β〉. Schreibweise: α →β.

Kontextfreie Grammatiken

Eine Kontextfreie Grammatik G = 〈Φ,Σ,R,S〉 besteht aus:
1. Nichtterminalsymbolen Φ
2. Terminalsymbolen Σ
3. Regelmenge R ⊆ Φ × Γ^∗ (Γ = Φ ∪ Σ)
4. Startsymbol S ∈ Φ

Beispiel 13.4.10 (Kontextfreie Grammatik).

G₁ = 〈{S,NP,V P,EN,V,D,N},{Egon,Pudel,den,ass},R,S〉
Regelmenge $(| S → N P VP, N P → EN, N P → D N, )| |{ V P → V N P, EN → Egon, N → Pudel, |} R = ||( V → ass, D → den ||)$

Ableiten von Sätzen

Deﬁnition 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:

es gibt eine Regel der Form w →z
die Zeichenketten u und v können so in Teilzeichenketten aufgeteilt werden, dass gilt: u = u₁wu₂ sowie v = u₁zu₂

Deﬁnition 13.4.12 (Ableitung (derivation)). Eine Ableitung ist ein n-Tupel 〈w₁,…,w_n〉 von Zeichenketten w_i ∈ Γ^∗ mit (1 ≤i ≤n) , so dass gilt:

w_i−1 ⇒w_i für alle i ∈{2..n}

Normale Schreibweise für Ableitungen

w₁ ⇒… ⇒w_n

Beispiel: Ableitung mit kontextfreier Grammatik

pict


Ableitung	u	Regel	v

	u₁wu₂	w →z	u₁zu₂


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

Deﬁnition 13.4.13 (Ableitungsrelation (derivation relation)). Die Ableitungsrelation ∗
⇒ ist die reﬂexiv-transitive Hülle von ⇒.

Deﬁnition 13.4.14 (Satz). Ein Satz a einer Grammatik G = 〈Φ,Σ,R,S〉 ist eine Zeichenkette aus Terminalsymbolen a ∈ Σ^∗, so dass gilt:

S +⇒ a

Deﬁnition 13.4.15 (Sprache einer Grammatik G). Die Sprache L_G einer Grammatik G = 〈Φ,Σ,R,S〉 ist 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

[ Zurück ] [ Zurück (Seitenende) ] [ Seitenbeginn ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]