FSK8-1 Entscheiden des Wortproblem für Sprachen von Typ 1
Aufgabenstellung
Sei eine Grammatik mit Produktionen
a) Berechnen Sie gemäß der Konstruktion aus der Vorlesung für alle 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 und Wort nach endlicher Zeit entscheidet, ob oder gilt.
: alle Satzformen der Länge die in höchstens Schritten vom Startsymbol aus ableitbar sind
Erster Schritt
Startzustand
Ableiten
Die Ableitungen zeigen die schrittweise Transformation der Startform in verschiedene Formen, die innerhalb von höchstens sechs Schritten erreicht werden können. Die genaue Berechnung kann je nach Ableitungsweg weitere Zwischenformen enthalten.