Das Ziel dieser Arbeit ist es, einen Rahmen für die Modellierung sprachbeschränkter Wegeprobleme in Graphen zu schaffen. Von konzeptioneller Seite sind da kontextfreie Grammatiken und Semiringe zu nennen. Kontextfreie Grammatiken erlauben die Beschreibung rekursiver generativer Prozesse, wie sie beispielsweise in der Grammatik natürlicher Sprache auftauchen oder zur Beschreibung von Zellwachstum dienen können. Sie erfassen außerdem die Struktur einiger dynamischer Programmierschemata, so wie sie zum Beispiel im CYK Algorithmus für kontextfreies Parsing oder in manchen pseudopolynomiellen Algorithmen für schwere Probleme benutzt werden. Die Verbindung kontextfreier Grammatiken mit Wegeproblemen in Graphen erlauben die Modellierung zusätzlicher formalsprachlicher Einschränkungen der möglichen Wege. Auf der anderen Seite können kontextfreie Grammatiken analog zum algebraischen Wegeproblem mit Semiringwerten ausgestattet werden. Im vierten Kapitel dieser Arbeit werden diese Beziehungen zwischen semiringbewerteten kontextfreien Grammatiken und Wegeproblemen näher untersucht. Diese Verbindung ist fruchtbar und erlaubt einen konzeptionellen Rahmen für Verallgemeinerungen des Wegeproblems für Graphen, beispielsweise zur Formulierung von Polynomialzeitalgorithmen für Transportprobleme welche sonst gar nicht oder nur umständlich als konventionelle Wegeprobleme dargestellt werden können. Wie sich beobachten lässt, können formalsprachliche Einschränkungen dazu führen, dass die erlaubten Wege exponentiell lang werden. Persistente Arrays, welche als binäre Bäume dargestellt werden, erlauben mit diesem Problem umzugehen und erhalten die Eigenschaft der Polynomialzeitberechenbarkeit. Allerdings wirft die Darstellung bestimmter exponentiell langer Wege in polynomiellem Platz die Frage auf, welche Berechnungen überhaupt auf sie angewandt werden können. Tatsächlich scheint sogar die Bestimmung, ob zwei solche Arrays äquivalent sind, schwer durchführbar zu sein. Im dritten Kapitel zeigen wir neben anderen Algorithmen für persistente Arrays einen probabilistischen Äquivalenztest. Persistente Arrays als solche werden bereits im ersten Kapitel kurz vorgestellt. Dort zeigen wir auch, dass das "Zippen" zweier persistenter Arrays exponentieller Länge, welche als Bäume dargestellt werden, im Allgemeinen nicht in einer Zeit durchgeführt werden kann, welche polynomiell zu deren Größe im Speicher wächst. Das zweite Kapitel führt in Wegeprobleme in Graphen ein. Der erste Abschnitt befasst sich mit Wegeproblemen in dynamischen Wäldern. Auch wenn der resultierende Algorithmus nicht so schnell wie die bestbekannten Algorithmen ist, erlaubt er eine einfache Implementierung, falls persistente Arrays bereits in einer Programmierbibliothek vorhanden sind. Wir stellen außerdem Semiringe und das algebraische Wegeproblem in Verbindung mit persistenten Arrays vor. Kapitel 5. zeigt einige Ergebnisse aus der Theorie formaler Sprachen, welche sich während dieser Arbeit ergeben haben. In Kapitel 6. zeigen wir weiterhin, wie Rytters Formulierung von Valiants subkubischem Algorithmus für kontextfreies Parsing mit Semiringparsing und Wegeproblemen in Verbindung steht.