Wortproblem

Das Wortproblem

Das Wortproblem ist ein fundamentales Problem in der Theorie der formalen Sprachen und Grammatiken. Es geht darum, für eine gegebene Grammatik und ein Wort zu entscheiden, ob dieses Wort von der Grammatik erzeugt werden kann oder nicht. Diese Fragestellung ist von großer Bedeutung, da sie Aufschluss über die Berechenbarkeit und Komplexität von Grammatiken und Sprachen gibt.

Formale Definition

Definition 3.3.1 (Wortproblem für Typ i-Grammatiken): Das Wortproblem für Typ i-Grammatiken ist die Frage, ob für eine gegebene Typ i-Grammatik $G=(V,\Sigma ,P,S)$ und ein Wort $w\in {\Sigma }^{\ast }$ gilt: $w\in L(G)$ oder $w\notin L(G)$.

Hierbei sind:

• $V$: die Menge der Nicht-Terminalsymbole,
• $\Sigma$: die Menge der Terminalsymbole,
• $P$: die Menge der Produktionen,
• $S$: das Startsymbol der Grammatik $G$.

$L(G)$ bezeichnet die von $G$ erzeugte formale Sprache.

Entscheidbarkeit für Typ 1-Grammatiken

Für kontextsensitive Grammatiken, auch als Typ 1-Grammatiken bekannt, ist das Wortproblem entscheidbar. Dieser Sachverhalt wird durch den folgenden Satz ausgedrückt:

Satz 3.3.2: Das Wortproblem für Typ 1-Grammatiken ist entscheidbar, d.h. es gibt einen Algorithmus, der bei Eingabe einer Typ 1-Grammatik $G$ und eines Wortes $w$ nach endlicher Zeit entscheidet, ob $w\in L(G)$ oder $w\notin L(G)$ gilt.

Die Intuition hinter diesem Satz ist, dass in jeder Ableitung $S\Rightarrow w_1\Rightarrow \cdots \Rightarrow w_m$ eines Wortes $w_m$ der Länge $n$ in einer kontextsensitiven Grammatik alle Satzformen $w_i$ höchstens die Länge $n$ haben. Da es nur endlich viele Satzformen der Länge $\le n$ über dem Alphabet $(\Sigma \cup V{)}^{\ast }$ gibt, kann man durch systematisches Durchprobieren all dieser Satzformen entscheiden, welche Wörter $w_m\in {\Sigma }^{\ast }$ der Länge $\le n$ von der Grammatik erzeugt werden und welche nicht.

Beachte, dass diese Berechnung für eine Typ 0-Grammatik falsch wäre, da dort zwischendrin auch Wörter der Länge $>n$ entstehen dürfen, die im Anschluss daran wieder gekürzt werden.

Ferner ist klar, dass die Berechnung von $L_m$ für ein gegebenes $m$ und $n$ terminiert. Die Mächtigkeit der Mengen $L_m$ ist durch $((|\Sigma \cup V|+1{)}^n)$ beschränkt (mehr Satzformen der Länge $\le n$ gibt es nicht). Für den Übergang von $L_{m-1}$ zu $L_m$ gilt $L_{m-1}=L_m$ oder $L_{m-1}\subset L_m$. Ferner gilt: Falls $L_{m-1}=L_m$, dann $L_{m-1}=L_{m+k}$ für alle $k\in \mathbb{N}$. Aus den vorherigen Aussagen folgt, dass es irgendein $m_0$ geben muss, für das $L_{m_0}=L_{m_0+k}$ für alle $k\in \mathbb{N}$ gilt. Nach Berechnung dieser Menge $L_{m_0}$ reicht es daher zu prüfen, ob $w\in L_{m_0}$ gilt oder nicht.

Daher entscheidet Algorithmus 2 das Wortproblem für Typ 1-Grammatiken.

Algorithmus 2: Entscheiden des Wortproblems für Typ 1-Grammatiken
Eingabe: Typ 1-Grammatik $G=(V,\Sigma ,P,S)$ (mit einer Sonderregel) und ein Wort $w\in {\Sigma }^{\ast }$
Ausgabe: Ja, wenn $w\in L(G)$, und Nein, wenn $w\notin L(G)$

Beginn
    n := |w|
    L := {λ}
    wiederhole
        L_old := L
        L := next(L_old, n)
    bis (w ∈ L) oder (L_old = L)
    wenn w ∈ L dann
        return Ja
    sonst
        return Nein
Ende

Beispiel

Betrachten wir die folgende kontextsensitive Grammatik $G$, die Palindrome über dem Alphabet $\Sigma =\{a,b\}$ erzeugt:

• $V=\{S,A\}$
• $\Sigma =\{a,b\}$
• $P=\{S\to \lambda ,S\to aSa,S\to bSb,A\to aAa,A\to bAb,A\to \lambda \}$
• $S$ ist das Startsymbol.

Wir können den oben beschriebenen Algorithmus verwenden, um zu entscheiden, ob ein gegebenes Wort $w$ von $G$ erzeugt wird oder nicht.

Zum Beispiel ist $w=abba$ ein Palindrom und gehört zu $L(G)$, da es durch die folgenden Ableitungen erzeugt werden kann:

$$S\Rightarrow aSa\Rightarrow abAba\Rightarrow abba$$

Im Gegensatz dazu gehört $w=abb$ nicht zu $L(G)$, da es kein Palindrom ist und daher nicht von $G$ erzeugt werden kann.

---