Grammatiken

Wort-Ersetzungs-Systeme

$$Id: rewriting.tex,v 1.1 2003/11/24 13:19:24 joe Exp $$

Berechnungs-Modell (Markov-Algorithmen)

• Zustand (Speicherinhalt): Zeichenfolge (Wort)
• Schritt: Ersetzung eines Teilwortes

Regelmenge $R \subseteq \Sigma^* \times \Sigma^*$

Regel-Anwendung: $u \to_R v \iff \exists x,z\in\Sigma^*, (l,r) \in R: u = x \cdot l\cdot z \wedge x \cdot r \cdot z = v$.

Beispiel: Bubble-Sort: $\{ba \to ab, ca \to ac, cb \to bc\}$

Beispiel: Potenzieren: $ab \to bba$

Aufgaben: gibt es unendlich lange Rechnungen für: $R_1 = \{ 1000 \to 0001110 \}, R_2= \{ aabb \to bbbaaa \}$?

Grammatiken

$$Id: grammatik.tex,v 1.3 2003/11/24 14:27:00 joe Exp $$

Grammatik $G$ besteht aus:

• Terminal-Alphabet $\Sigma$

  (üblich: Kleibuchst., Ziffern)

• Variablen-Alphabet $V$

  (üblich: Großbuchstaben)

• Startsymbol $S \in V$
• Regelmenge
  $R \subseteq (\Sigma\cup V)^* \times (\Sigma\cup V)^*$

Grammatik
  { terminale 
       = mkSet "abc"
  , nichtterminale 
       = mkSet "SA"
  , startsymbol = 'S'
  , regeln = mkSet
       [ ("S", "abc")
       , ("ab", "aabbA")
       , ("Ab", "bA")
       , ("Ac", "cc")
       ]
  }

von $G$ erzeugte Sprache: $L(G) = \{ w \mid S \to^* w \wedge w \in \Sigma^* \}$.

Eingeschränkte Grammatiken

$$Id: chomsky.tex,v 1.3 2003/11/24 14:27:00 joe Exp $$

Für allgemeine Grammatiken ist $w \in L(G)$ (Wortproblem) gar nicht entscheidbar.

Regelmenge einschränken $\to$

• Vorteil: leichter (automatisch) zu behandeln
• Nachteil: weniger ausdrucksstark

Die Chomsky-Hierarchie

• Typ-0 (beliebige Regeln)

  (Wortproblem nicht entscheidbar)

• Typ-1 (keine verkürzenden Regeln): $\forall (l,r) \in R: \vert l\vert \le \vert r\vert$.

  ( $\Rightarrow$ Wortproblem entscheidbar, jedoch aufwendig)

• Typ-2 (nur kontextfreie Regeln): $\forall (l,r) \in R: l \in V$

  ( $\Rightarrow$ Wortproblem in Polynomialzeit)

• Typ-3 (nur rechtslineare Regeln):

  $\forall (l,r) \in R: l \in V \wedge r \in \Sigma V \cup \Sigma$.

  ( $\Rightarrow$ Wortproblem in Linearzeit)

Theorie der Formalen Sprachen

$$Id: theorie.tex,v 1.3 2003/11/24 14:27:00 joe Exp $$

untersucht (Hierarchien von) Sprachfamilien:

• äquivalente Definitionen für Familien (Grammatiken, Automaten, Ausdrücke)
• (echte) Inklusionen (ist jede Typ-2-Sprache eine Typ-1-Sprache? gibt es Typ-2-Sprachen, die keine Typ-3-Sprache sind?)
• Abschluß der Familien bzgl. Operationen (ist der Durchschnitt von zwei Typ-3-Sprachen wieder Typ-3? Desgl. für Typ-2?) (Falls ja, wie konstruiert man ihn effektiv?)
• Entscheidbarkeit/Komplexität (z. b. des Wort-Problems)

Theorie (II)

$i \ge j \Rightarrow$ Jede Typ-$i$-Sprache ist eine Typ-$j$-Sprache.

$i > j$: es gibt $L$ in Typ-$j$ $\setminus$ Typ-$i$:

$\{ a^n b^n \mid n \ge 0\} \in$ Typ-$2$ $\setminus$ Typ-$3$.

$\{ a^n b^n c^n \mid n \ge 0\} \in$ Typ-$1$ $\setminus$ Typ-$2$.

Wenn $A, B \in \operatorname{Typ-}3$, dann $A\cup B\in \operatorname{Typ-}3$ (trivial) und $A \cap B\in \operatorname{Typ-}3$ (Aufgabe -- benutze Automaten).

Wenn $A, B \in \operatorname{Typ-}2$, dann $A\cup B\in \operatorname{Typ-}2$ (trivial -- Aufgabe).

Es gibt $A, B \in \operatorname{Typ-}2$ mit $A \cap B \notin \operatorname{Typ-}2$.

Typ-3-Grammatiken und Reguläre Sprachen

$$Id: reg.tex,v 1.3 2003/11/24 14:27:00 joe Exp $$

Def (Wdhlg): $L$ heißt regulär $\iff$ existiert regulärer Ausdruck $X$ mit $L=L(X)$.

Satz (Wdhlg): $L$ regulär $\iff$ existiert endlicher Automat $A$ mit $L = L(A)$. (Beweis: Analyse/Synthese)

Satz: $L$ regulär $\iff$ existiert Typ-3-Grammatik $G$ mit $L=L(G)$. Beweis (trivial):

• Zustände von $A$ $=$ Variablen von $G$,
• Startzustand von $A$ $=$ Startsymbol von $G$
• jede Regel $p \stackrel{a}{\to} q$ in $A$ $=$ Regel $p \to aq$ in $G$

Sternhöhe

$$Id: star.tex,v 1.2 2003/11/24 14:27:00 joe Exp $$

Def: die Sternhöhe $\operatorname{SH}(X)$ eines regulären Ausdrucks $X$ ist die maximale Schachteltiefe der Sterne.

Bsp: $\operatorname{SH}((a^*b)^*) = 2$.

Def: die Sternhöhe $\operatorname{SH}(L)$ einer regulären Sprache $L$ ist $\min \{\operatorname{SH}(X) \mid L(X) = L \}$.

Bsp: $\operatorname{SH}((a^*b)^*) = 1$, denn $(a^*b)^* = \epsilon \cup \Sigma^*b$

Erweiterte Sternhöhe

Def: in erweiterten regulären Ausdrücken ist als zusätzlicher Operator Komplement bzgl. $\Sigma^*$ und Mengendifferenz gestattet.

Def: erweiterte Sternhöhe $\operatorname{ESH}(X)$ eines Ausdrucks wie oben als maximale Schachteltiefe, erweiterte Sternhöhe $\operatorname{ESH}(L)$ einer Sprache wie oben als kleinste $\operatorname{ESH}(X)$ mit $L(X)=L$.

Bsp: $\operatorname{ESH}((ab)^*) = 0$, denn $(ab)^* = \epsilon \cup a\Sigma^*b \setminus \Sigma^*(aa \cup bb) \Sigma^*$

beachte: $\operatorname{ESH}(\Sigma^*) = 0$ wegen $\Sigma^* =$ Komplement von $\emptyset$.

Vermutung: für jede reguläre Sprache $L$ gilt $\operatorname{ESH}(L)\le 1$.