Hi
a) Die Grammatik als Graph aufzeichnen: Einen Startknoten, eine Reihe anderer Knoten (ein paar davon sind gültige Endknoten), und zwischen welchen Knoten kann man (ein. oder beidseitig) herumspringen wenn man keine/folgende... Buchstaben dabei "verbraucht".
b) Das genau so in Java-Objekte umsetzen. Eine Klasse Knoten, die zwei boolean Start/End hat (die meisten Knoten haben vermutlich beides false, aber manche eben nicht). Und eine Klasse für Übergange (Außer dass man kein Ü in Variablennamen verwenden sollte), von welchem zu welchem Knoten, braucht man Buchstaben dafür ja/nein, und welche (ArrayList von char oder so). Davon genug Objekte im Programm natürlich auch anlegen und mit Daten füllen, idealerweise in eine Knoten-ArrayList und eine Übergang-ArrayList.
(Falls es auch Übergänge mit "von-bis", zB. A-Z gibt, muss es eben keine Arrayliste von einzelnen chars werden, sondern eine von jeweils zwei chars, Anfang und Ende des Bereichs)
Um ein Wort auf Gültigkeit zu überprüfen, beginnt man theoretisch am Startknoten,, nimmt den ersten Buchstaben, und geht am passenden Übergang zum nächsten Knoten. Beim aktuellen Knoten mit dem nächsten Buchstaben wiederholen, usw., bis das Wort aufgebraucht ist. Wenn man irgendwo steckt, weil es für den aktuellen Buchstaben im aktuellen Knoten keinen Übergang gibt, wird das Wort nicht akzeptiert. Wenn man am Ende bei einem Knoten ist, der nicht als Endknoten markiert ist, auch nicht akzeptiert.
Die Implementierung hängt davon ab, ob die Graphen sicher immer deterministisch sind oder nicht (nicht deterministisch = es kann vorkommen, dass man sich bei Knoten soundso und Buchstabe soundso zwischen mehreren möglichen Übergängen aussuchen kann)
c1) Deterministisch (einfacher):
Ziemlich gleich zur theoretischen Beschreibung. Eine Variable aktueller Knoten (entweder das Knotenobjekt selber oder der Index in der ArrayListe), und eine Variable für die Position im Wort machen.
Dann in einer Schleife: Zuerst alle Übergänge durchsuchen, welcher vom aktuellen Knoten ausgeht und den aktuellen Buchstaben akzeptiert. Falls nichts gefunden, nicht akzeptiert. Sonst, den Zielknoten zum neuen aktuellen Knoten machen, und die Buchstabenposition um 1 erhöhen.
Am Schluss noch prüfen ob der aktuelle Knoten die Endmarkierung hat, sonst auch nicht akzeptieren.
c2) Nichtdeterministisch:
Sobald man zur ersten Gabelung kommt hat man praktisch mehrere aktuelle Knoten weiterzuverfolgen. Man könnte das schön mit Rekursion lösen, dabei gibts aber ein Stackoverflow-Risiko. Ohne Rekursion:
Nicht einen aktuellen Knoten und Buchstabenpositition haben, sondern eine ArrayList davon (am Anfang nur ein Eintrag, Startknoten und 0 eben). In einer Schleife immer alle Einträge durchgehen, jeweils aus der Arraylist rausnehmen, wie die Einzelvariante oben behandeln, und ein/mehrere Zielknoten samt neuer Position wieder einfügen. Wenn man steckt, einfach nichts einfügen.
Sollte die Liste je leer werden, nicht akzeptieren.
Wenn man bei einem der verfolgten Pfade am Wortende ankommt und das kein Endknoten ist, auch nicht wieder in die Liste einfügen weil eben ungültig.