Spezifikation

Der Beweis von Satz 4 ist konstruktiver Natur und dient als Vorlage für einen Algorithmus:

Berechne reduzierte Grammatik G' mit L(G') = L(G) unter Verwendung der im Beweis von Satz 1 angegebenen Algorithmen 1 und 2.

Berechne Grammatik G'' ohne $\epsilon$ -Produktionen und ohne Kettenproduktionen mit L(G'') = L(G') $\setminus$ $\left\{\vphantom{\epsilon}\right.$ $\epsilon$ $\left.\vphantom{\epsilon}\right\}$ unter Verwendung der Algorithmen 3 und 4.

Berechne Grammatik G_CNF in Chomsky-Normalform mit L(G_CNF) = L(G'') = L(G') $\setminus$ $\left\{\vphantom{\epsilon}\right.$ $\epsilon$ $\left.\vphantom{\epsilon}\right\}$ = L(G) $\setminus$ $\left\{\vphantom{\epsilon}\right.$ $\epsilon$ $\left.\vphantom{\epsilon}\right\}$ mit dem Algorithmus 5 aus dem Beweis von Satz 4.

Das Programm soll diesen Ablauf veranschaulichen. Dazu muss es die Alphabet- und die Metazeichen und insbesondere die Produktionen einer Grammatik anzeigen und nach einem Schritt in der Rechnung sollen die Ausgangsgrammatik und die erhaltene Grammatik nebeneinander dargestellt werden. Dabei sollen Unterschiede (also Rechenergebnisse) hervorgehoben werden.

Es soll zwei Algorithmus-Ebenen geben, die jeweils im Schritt- oder im Filmmodus sind:

Die ''obere'' Ebene behandelt den Ablauf von einer kontextfreien Grammatik zu einer produktiven, einer reduzierten, einer ohne nullierbare Nichtterminale, einer ohne $\epsilon$ -Produktionen über eine ohne Kettenproduktionen bis schliesslich zur Grammatik in Chomsky-Normalform. Ein Schritt wäre hier also z.B. der Übergang von einer produktiven zu einer reduzierten Grammatik durch Entfernung der nicht erreichbaren Zeichen, ohne dieses Vorgehen zu demonstrieren.

Die ''untere'' Ebene behandelt den Ablauf, der notwendig ist, um die Übergänge der oberen Ebene zu realisieren. Es gibt also pro Schritt auf der oberen Ebene eine komplette untere Ebene. Im Beispiel wäre dann ein Schritt auf der unteren Ebene z.B. die Hinzunahme eines Metazeichens zur Menge der erreichbaren.

Im Schrittmodus soll das Programm immer genau einen Schritt ausführen und dann auf eine Eingabe warten, im Filmmodus sollen die Schritte nacheinander vorgeführt werden, ohne das eine Eingabe notwendig ist. Dabei sind die Einstellungen für die untere Ebene wirkungslos, wenn die obere im Filmmodus ist.

Es muss möglich sein, Produktionen hinzuzufügen und zu löschen. Dabei werden die Meta- und die Alphabetzeichen aus den eingegebenen Produktionen automatisch ermittelt. Alle Hilfetexte werden in einer HTML-Seite zusammengefasst, in die das fertige Applet eingebunden ist und die Nutzer sollen immer über den aktuellen Programmstatus informiert werden.

Die sich so ergebende Grobaufteilung der Benutzerschnittstelle ist in Abbildung 1 dargestellt.

**Abbildung 1:** Grobskizze des Userinterface
$\begin{figure}\begin{center}\newlength{\save}\setlength{\save}{\fboxsep}\setle... ...0.5){bFilmU}}}} \end{picture}\setlength{\fboxsep}{\save}\end{center}\end{figure}$