WortKFG-Algorithmus

Einfache Sprache

Idee WortKFG-Algorithmus

Der WortKFG gibt für ein Kontextfreie Grammatik $\mathcal G$ und ein Wort über dessen Terminalsymbole $w\in T^*$ an, ob das Wort in der produzierte Sprache von $\mathcal G$ ist.

  	\begin{algorithm}
	\caption{WortKFG}
	\begin{algorithmic}
	\Input $\textrm{Kontextfreie Grammatik } \mathcal G = (T, V, S, P) \textrm{, Wort } w\in T^*$
	\State $n\gets |w|$
	\State $\Delta\gets \{\langle i,w(i),i+1\rangle: i< n\}$
    \State Let $\mathcal A = (Q,\Sigma,\delta,\{0\},\{n\})$ be a NFA with $Q := \{0,\ldots,n\}$ und $\delta(i,v)\to\{j:\langle i, v, j\rangle\in\Delta\}$
    \While{$\exists A\in V,i,j\in[0,n],\alpha\in\Sigma^*:\langle i,A,j\rangle\not\in\Delta\land A\to \alpha\in P$ and $\alpha$ can be read in $\mathcal A$ from $i$ to $j$}
	    \State $\Delta\gets\Delta\cup\{\langle i,A,j\rangle\}$
    \EndWhile
    \If{$\langle 0, S, n\rangle\in \delta$}
        \Return $w\in\mathcal G$
    \Else
		\Return $w\not\in\mathcal G$
    \EndIf
	\end{algorithmic}
	\end{algorithm}

Beispiel

Gegeben die Kontextfreie Grammatik $S\to \varepsilon\;|\;SS\;|\;(S)\;|\;[S]$ wobei $T = \{(,),[,]\}$ und das Wort $w = ()[]$.

Wir beginnen mit $\Delta = \{\langle 0, (,1\rangle, \langle 1, ),2\rangle, \langle 2, [,3\rangle, \langle 3, ],4\rangle\}$

Wir fügen zunächst für alles Fälle in denen $i=j$ ist jeweilst $\langle i,S,i\rangle$ wegen der Regel $S\to\varepsilon$. Dann fügen wir $\langle 0,S,2\rangle$ ein wegen der Regel $S\to (S)$ und $\langle 2,S,4\rangle$ ein wegen der Regel $S\to [S]$. Schlussendlich noch $\langle 0,S,4\rangle$ wegen der Regel $S\to SS$. Wir erhalten folgendes Automaten $\mathcal A$:

Home: