Suche Home Einstellungen Anmelden Hilfe

2.1 Algorithmus

Der folgende Algorithmus berechnet alle Tij, mit 1 i < n - j +1. Anfänglich haben alle Tij die leere Menge als Wert. für i = 1 bis n tue Ti1 = { A | so dass Axi eine Regel in P ist} Die erste Zeile enthält alle Nichtterminale, die das Eingabesymbol an der entsprechenden Position ableiten. Ende_tue; für j = 2 bis n tue  Für jede weitere Zeile ... für i = 1 bis n - j +1 tue  ... und jede Zelle dieser Zeile von links nach rechts: für k = 1 bis j-1 tue  berechne das jeweils zu betrachtende Zellenpaar. k' = i + k; j' = j - k; Tij = Tij { A | so dass ABC eine Regel in P ist, B in Tik und C in Tk'j' liegt} Nun überprüfe man für jedes Zellenpaar (anfänglich Ti1 und T(i-1)(j-1), dann Ti2 und T(i-2)(j-2), usw.), ob eine Kombination dort enthaltener Nichtterminale eine rechte Regelseite ergibt. Das Terminalsymbol der dazu gehörenden linken Regelseite füge man Tij hinzu. Ende_tue; Ende_tue; Ende_tue; falls S Tij dann gebe_aus "w liegt in L(G)" sonst gebe_aus "w liegt nicht in L(G)" Zur Komplexität des Algorithmus gibt es auf Niveaustufe 3 weitere Informationen.

Methode 1   2   3   4   5 Linksparse

Benutzer: Gast • Besitzer: matthias • Zuletzt geändert am: