FSK-ÜB-8

FSK8-1 Entscheiden des Wortproblem für Sprachen von Typ 1

Aufgabenstellung

Sei $G=(V,\{a,b,c\},P,S)$ eine Grammatik mit Produktionen

$$\begin{array}{rl}P=\{S& \to SabS\mid Ac\mid cB,\\ Ac& \to ccA,\\ cA& \to ca,\\ AA& \to aA,\\ Aa& \to ab,\\ cB& \to Bcc,\\ Bc& \to bc,\\ BB& \to Bb,\\ bB& \to ab\}\end{array}$$

a) Berechnen Sie gemäß der Konstruktion aus der Vorlesung $L_i^6$ für alle $i\in \mathbb{N}$ und begründen Sie kurz.

Satz 3.3.2.

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

$L_i^6$: alle Satzformen der Länge $n$ die in höchstens $m$ Schritten vom Startsymbol aus ableitbar sind

Erster Schritt

Startzustand

$$\begin{array}{rl}{L}_0^6& =\{SabS\}\\ L_1^6& =\{SabSabS,SabAc,SabcB,AcabS,cBabS\}\\ L_2^6& =\{SaccA,SacBcc,Sabca,AccA,cAabS,BcccA,BccBcc,cBabca,\dots \}\\ L_3^6& =\{SabSabSabS,SabSabAc,SabSabcB,SabAccA,SabAcBcc,SabcBccA,\dots \}\end{array}$$

Ableiten

$$\begin{array}{rl}{L}_0^6& =\{SabS\}\\ L_1^6& =\{SabAc,SabcB,AcabS,cBabS\}\\ L_2^6& =\{SaccA,SacBcc,Sabca,AccA,cAabS,BcccA,BccBcc,cBabca,\dots \}\\ L_3^6& =\{SabbccA,SabBccc,SabSabAc,SabSabcB,SabAccA,SabAcBcc,SabcBccA,\dots \}\end{array}$$

Die Ableitungen zeigen die schrittweise Transformation der Startform $SabS$ in verschiedene Formen, die innerhalb von höchstens sechs Schritten erreicht werden können. Die genaue Berechnung kann je nach Ableitungsweg weitere Zwischenformen enthalten.

b) Geben Sie zwei Wörter an die auf Grundlage der Berechnung in der Sprache $L(G)$ sind.

1. $SabbccA$
2. $SabAccA$

c) Geben Sie drei Wörter an die auf Grundlage der Berechnung nicht in der Sprache $L(G)$ sind.

1. $abcc$
2. $abAc$
3. $Sab$

---