next up previous contents index
Next: Syntaxbäume 23 Up: Allgemeines zu Sprachen Previous: Chomsky-Hierarchie 17   Contents   Index

Subsections


Wortproblem 21

Das Wortproblem für Typ 1-Sprachen (und damit auch für Typ 2 ,3) ist entscheidbar. Es gibt einen Algorithmus, der bei Eingabe einer kontextsensitiven Grammatik $ G=\left(V,\Sigma,P,S\right)$ und eines Wortes $ x\in\Sigma^{*}$ in endlicher Zeit entscheidet, ob $ x\in L\left(G\right)$ oder $ x\notin L\left(G\right)$.

Algorithmus zum Lösen des Wortproblems bei Typ 1 - Grammatiken

Vorweg zur Notation: Bei $ T_{n}^{m}$ handelt es sich um die Menge aller Satzformen, die maximal $ m$ Symbole haben, und in maximal $ n$ Ableitungsschritten aus dem Startsymbol $ S$ ableitbar sind.

Um das Wortproblem für ein Wort $ w\in\Sigma^{*}$ mit der Länge $ \left\vert w\right\vert=m$ zu lösen, muss geprüft werden, ob es in der Menge $ T_{n}^{m}$ (mit genügend großem $ n$) enthalten ist. $ T_{n}^{m}$ lässt sich wie folgt konstruieren:

Dieser Algorithmus hat eine Laufzeit von $ O\left(c^{n}\right)$


next up previous contents index
Next: Syntaxbäume 23 Up: Allgemeines zu Sprachen Previous: Chomsky-Hierarchie 17   Contents   Index
Marco Möller 18:11:27 24.10.2005