Menu
Willkommen bei XWizard: Das Online-Informatik-Tool

Anleitung zum XWizard

XWizard (eXercise Wizard) ist ein Werkzeug zur Erstellung und Visualisierung mathematischer Objekte verschiedenster Art. Er wurde entwickelt, um sowohl Lehrende als auch Lernende bei der Veranschaulichung theoretischer Konzepte zu unterstützen. Zu den derzeit implementierten Objekttypen gehören unter anderem Turingmaschinen, endliche Automaten, Kellerautomaten, Chomsky Grammatiken und verschiedene Arten von Suchbäumen. Um ein bestimmtes Objekt zu definieren, muss ein Skript mit entsprechender Syntax (wie unten beschrieben) in das Skript-Feld auf der Startseite eingegeben werden. Sobald das Objekt generiert wurde, können mittels der dafür zur Verfügung stehenden 'Konversions-Buttons' Algorithmen wie z.B. Automatenminimierung, Syntax-Analyse und viele andere darauf angewendet werden. Genauer gesagt transformieren diese Algorithmen das Skript, das dem aktuellen Objekt zugrundeliegt, in ein anderes Skript, das einen anderen Objekttypen beschreibt. Dadurch ändert sich auch die Darstellung dieses neuen Objektes. Strenggenommen stellen Skripte den ausschließlichen Kontrollmechanismus im XWizard dar, daher kann ein Klick auf einen beliebigen Button immer durch das Einfügen eines entsprechende Skriptes ersetzt werden. Andererseits können viele Operationen auch einfach mittels der graphischen Oberfläche (Buttons usw.) ausgeführt werden, ohne dass man sich Gedanken um das passende Skript machen muss.

Die Beispiele, die auf der Startseite zur Verfügung stehen, können als Ausgangspunkt zur Erstellung eines Skriptes des jeweiligen Typs verwendet werden. Bei Problemen mit einem Skript können die Hilfetexte unten weiterhelfen, oder ein Klick auf den Link   discuss this script  unterhalb des Skript-Feldes, um Hilfe in der Community zu bekommen.

Der XWizard wurde ursprünglich zur Unterstützung der Vorlesung → Info II am → KIT entwickelt, beinhaltet inzwischen aber auch Skript-Typen, die darüber hinausgehen. Zusätzlich zu dieser web-basierten Version ist auch die Desktopversion PDF-XWizard → auf Sourceforge als kostenloser Download erhältlich. Sie stellt zusätzliche Funktionen zur Verfügung und verzichtet auf jegliche Einschränkungen bezüglich Skriptgröße oder Rechenzeit.

Falls Sie Interesse haben, sich dem XWizard-Entwicklungs-Team anzuschließen, etwa um eigene Skript-Typen zu implementieren, wenden Sie sich bitte per Email an → lukas.koenig@kit.edu.

Übungsmodus

Außer dem normalen Modus, in dem alle Konversionsmethoden zur Verfügung stehen und mit allen Skript-Typen gearbeitet werden kann, kann der XWizard auch im sogenannten Übungsmodus betrieben werden. In diesem Fall wird eine Aufgabe gestellt, die gelöst werden soll. Dabei können einige Konversionsbuttons verborgen sein, damit die Lösung der Aufgabe mit den verbleibenden Methoden erfolgen muss. Außerdem kann das Skript der Aufgabe ganz oder teilweise verschlüsselt sein, damit der Inhalt nicht zum Schummeln genutzt werden kann. Wenn die Aufgabe richtig gelöst wurde, wird ein Bonus (ein geheimes Wort) angezeigt, und der XWizard kehrt in den normalen Modus zurück.

Es können auch eigene, individuelle Aufgaben erstellt werden, bspw. durch Anklicken des Buttons   erzeuge aufgabe aus skript  . Um eine Aufgabe (oder beliebige andere Skripte) zu archivieren und zu teilen, kann daraus mit Hilfe des Buttons   erstelle url zu diesem skript   eine URL erstellt werden. Um sehr lange URLs zu vermeiden, können Aufgaben und (fast) alle anderen Skript-Typen auch mit Hilfe des Buttons   erstelle kurze url zu diesem skript   in eine Kurz-URL konvertiert werden.

Technisches

XWizard bearbeitet komplexe Objekte, die zum Teil unberechenbare (im Turing-Sinn) Eigenschaften haben können (insbesondere Grammatiken und Turingmaschinen haben viele solche Eigenschaften). Daher können manche Algorithmen in sehr lange oder sogar endlos laufende Schleifen laufen, die nicht im Vorfeld erkannt und ausselektiert werden können. XWizard wird die entsprechenden Algorithmen also trotzdem starten und erst nach einer gewissen Laufzeit unterbrechen, wenn sie zu lange gelaufen sind (oder zuviel Speicher benötigt haben). In vielen dieser Fälle wird eine Fehlermeldung ausgegeben, in einigen seltenen Fällen wird die ausgewählte Operation einfach nicht beendet und der Vorzustand wiederhergestellt. In jedem Fall aber (zumindest soweit wir wissen), wird XWizard innerhalb seines vorgesehen Zustandsraums bleiben, d.h., er wird stabil laufen. Wir werden in Zukunft daran arbeiten, noch etwas schönere Fehlermeldungen auszugeben, aber da die Wurzel des Problems nicht gelöst werden kann, sind weder schöne noch hässliche Fehlermeldungen als Zeichen der Instabilität zu werten. (Wenn allerdings die Seite nicht mehr reagiert oder HTML- oder Java-Fehler ausgegeben werden, können Sie uns → hier Bescheid sagen.)

Cookies: XWizard speichert eine Zufallszahl als Cookie auf dem Rechner des Benutzers. Sie wird ausschließlich dazu verwendet, diesen beim nächsten Mal wiederzuerkennen und dessen Einstellungen zu reaktivieren. Wenn Cookies ausgeschaltet sind, können persönlichen Einstellungen (wie Sprache, Modus etc.) nicht korrekt wiederhergestellt werden.

Bekannter Fehler 1: Wenn der   zurück  -Button des Browsers verwendet wird, funktioniert direkt danach der Button   pdf herunterladen   nicht richtig. Durch Anklicken des Buttons   draw!   kann die Funktionalität wiederhergestellt werden.

Bekannter Fehler 2: Wenn das aktuelle Skript durch eine Konversionsmethode entstanden ist, dann kann die Kurz-URL nicht erzeugt werden. Durch Anklicken des Buttons   draw!   kann die Funktionalität wiederhergestellt werden.

Hilfe zu 'Endlicher-Automat'

Ein Endlicher Automat (EA; auch Zustandsmaschine oder Zustandsautomat, engl. Finite State Machine), ist ein mathematisches Berechnungsmodell. Neben seiner Anwendung in der Theoretischen Informatik wird er in der Praxis beim Entwurf sowohl von Computerprogrammen als auch von logischen Schaltkreisen verwendet. Ein EA kann als abstrakte Maschine begriffen werden, die sich zu jedem gegebenen Zeitpunkt in einem bestimmten Zustand befindet (bezeichnet als momentaner Zustand), der zu einer endlichen Menge möglicher Zustände gehört. Der Übergang von einem Zustand in einen anderen wird Transition genannt und hängt von einer auslösenden Bedingung ab. Wir geben diese Bedingung durch ein Zeichen aus einem Eingabealphabet an. Ein bestimmter EA wird definiert durch eine Liste seiner Zustände und die auslösende Bedingung für jede Transition.

Es ist zu beachten, dass der momentane Gesamtzustand eines nichtdeterministischen EA auch aus mehreren Zuständen oder aus überhaupt keinem bestehen kann. Grundsätzlich bleibt jedoch die obige Beschreibung gültig, da jede Teilmenge von Zuständen eines nichtdeterministischen EA als einzelner Zustand eines äquivalenten deterministischen EA betrachtet werden kann. (Vgl. die → Potenzmengenkonstruktion, um einen nichtdeterministischen EA in einen deterministischen umzuwandeln.)

Das Verhalten von EAs bildet viele reale Anwendungsfälle ab, in denen Maschinen vordefinierte Sequenzen von Aktionen ausführen, die von einer Sequenz von zugehörigen Ereignissen abhängen. Einfache Beispiele hierfür sind Getränkeautomaten, die Waren ausgeben, nachdem eine ausreichende Zahl an Münzen eingeworfen wurde, Aufzüge, die Passagiere in höheren Stockwerken absetzen, bevor sie nach unten fahren, Ampeln, die ihre Schaltung ändern, wenn Autos warten, und Zahlenschlösser, bei denen die richtige Kombination in der richtigen Reihenfolge eingegeben werden muss. Weitere Einzelheiten bezüglich Endlicher Automaten können → hier nachgelesen werden.

Vorgehensweise im XWizard:

  • Ein Skript wird mit fsm: (für Finite State Machine) begonnen, um anzuzeigen, dass es sich um einen EA handelt.
  • Eine Liste aller Transitionen definiert das Verhalten des Automaten, jede einzelne von der Form: (s0, a) => s1; (Bedeutung: Übergang von Zustand s0 in Zustand s1, unter der Bedingung, dass a gelesen wird).
  • Die Liste aller Zustände, sowie die Symbole des Eingabealphabets werden nicht explizit angegeben. Wird eine Transition gelesen, wird automatisch angenommen, dass die gegebenen Zustände (s0, s1 im obigen Beispiel) sowie die Eingabesymbole (a im obigen Beispiel) Teil des EA sind.
  • Der Anfangszustand (s0) und die Liste der Endzustände (F) müssen im Deklarations-Bereich definiert werden (klicke auf den grauen Konversions-Button   skript formatieren   oder   deklarationen hinzufügen  , um den Deklarations-Bereich zum Skript hinzuzufügen).
  • Durch klicken auf   simuliere einen schritt  , kann ein Eingabewort angegeben werden, für das das Verhalten des EA schrittweise durch wiederholtes Klicken auf denselben Button simuliert wird (dasselbe kann man erreichen, indem man ein input-Wort und einen simulateToStep-Wert im Deklarations-Bereich angibt).
  • Wird ein deterministischer EA definiert, erzeugt ein Klick auf   minimiere   einen äquivalenten minimalen EA.
  • Ein Klick auf   zeige minimierungstabelle   zeigt die entsprechende Minimierungstabelle an (auch nur im deterministischen Fall).
  • Wird ein nichtdeterministischer EA definiert, erzeugt ein Klick auf   mache deterministisch   einen äquivalenten deterministischen EA.
  • Für jeden EA können durch einen Klick auf   zeige minimierungs-ablauf   Informationen zum Determinierungs- und Minimierungsprozess angezeigt werden.
  • Der EA kann durch Klick auf den entsprechenden Button in einen äquivalenten Kellerautomaten konvertiert werden (  kellerautomat  ), in eine Turingmaschine (  turingmaschine  ), in eine rechtslineare Grammatik (  rechtslineare grammatik  ) oder in einen Regulären Ausdruck (  regulärer ausdruck  ).

Konversions-
methoden
Konversion in Zufälliger Automat...
X

Erzeuge neuen, zufälligen endlichen Automaten. Bitte Parameter eingeben:

arg0: (int: Die Anzahl der Zustände im zufälligen Automaten.)
arg1: (boolean: Setze diesen Parameter auf true, um einen deterministischen Automaten zu erzeugen.)

Zufälliger Automat (mit Seed)...
X

Erzeuge neuen, zufälligen endlichen Automaten unter Angabe eines Seed-Werts für den Zufallsgenerator Bitte Parameter eingeben:

arg0: (int: Die Anzahl der Zustände im zufälligen Automaten.)
arg1: (boolean: Setze diesen Parameter auf true, um einen deterministischen Automaten zu erzeugen.)
arg2: (long: Der Seed für den Zufallsgenerator.)

Simuliere einen Schritt...
X

Simuliere endlichen Automaten für einen Schritt Bitte Parameter eingeben:

arg0: (String: Gib ein Eingabewort ein, auf dem der Automat simuliert werden soll.)

Für Lehrende Animiere EA-Simulation...
X

Standardanimation zur Simulation eines gegebenen Inputworts. Bitte Parameter eingeben:

arg0: (String: Gib ein Eingabewort ein, auf dem der Automat simuliert werden soll.)

Erzeuge Aufgabe aus Skript...
X

Erzeuge ein Aufgaben-Skript aus diesem Skript. Bitte Parameter eingeben:

arg0: (String: Eine kurze Beschreibung oder einen Titel für die Aufgabe.)
arg1: (String: Eine lange Beschreibung der Aufgabe ein (HTML erlaubt).)
arg2: (String: Optional kann hier ein Lösungs-String für die Aufgabe angegeben werden.)
arg3: (String: Optionaler Belohnungscode, den der Benutzer durch das Lösen der Aufgabe verdienen kann.)
arg4: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Methodenname.)
arg5: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Skript-Klasse.)
arg6: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Zielklasse.)
arg7: (String: Optionaler Erklärungstext, der zusammen mit der Lösung angezeigt wird.)
arg8: (boolean: Auf true gesetzt wird die Verschlüsselung der Aufgabe - nicht des gesamten Skripts - veranlasst.)
arg9: (boolean: Auf true gesetzt wird die Verschlüsselung des gesamten Skripts veranlasst.)

Debuggen Schrittweise Script-Evaluation...
X

Erzeugt eine Animation der Expansion dieses Skripts zum Debuggen. (Es gibt nichts zu expandieren.) Bitte Parameter eingeben:

arg0: (Boolean: Auf true gesetzt, werden auch die in jedem Schritt verfügbaren Preprozessoren angezeigt.)

Beispiel:

→ Draw!




Zusammenfassen/Auseinanderziehen von Regeln: Skripte dieses Typs basieren auf sogenannten Regeln, etwa: X => Y; Regeln können über den Button   skript formatieren   (oder von Hand) folgendermaßen zusammengefasst werden:

A => B;
A => C;
A => D;
wird zu:
A => B | C | D;

...und ebenso:

A => D;
B => D;
C => D;
wird zu:
A | B | C => D;

...und sogar:

A => C;
A => D;
B => C;
B => D;
wird zu:
A | B => C | D;

Zusammengefasste und auseinandergezogene Regeln haben denselben Informationsgehalt, sie sind also in der oben gezeigten Weise austauschbar.

Hilfe zu 'Kellerautomat'

In der Informatik versteht man unter einem Kellerautomaten (KA) ein Berechnungsmodell, das ein Band verwendet (vgl. Turingmaschine), auf das nur im 'Last-In-First-Out' Verfahren zugegriffen werden kann. Dieses wird als → Stapelspeicher oder Keller bezeichnet. Die Bezeichnung Stapelspeicher (statt Keller) illustriert, wie neue Elemente im Speicher immer oben auf die bereits enthaltenen 'gestapelt' werden. Für jede Operation auf dem Speicher ist entsprechend auch immer nur das oberste Element verfügbar, es kann keines von unten 'hervorgezogen' werden, man muss sie Stück für Stück wieder freilegen.

Was die Berechnungsmächtigkeit angeht, sind KA leistungsfähiger als endliche Automaten, aber weniger leistungsfähig als Turingmaschinen. Genauer gesagt sind deterministische KA in der Lage, alle deterministischen kontextfreien Sprachen zu erkennen, während nichtdeterministische KA alle kontextfreien Sprachen erkennen können. Hauptsächlich erstere werden häufig beim Entwurf von → Parsern verwendet. Weitere Einzelheiten über Kellerautomaten können → hier nachgelesen werden.

Ein KA arbeitet ein Eingabewort von links nach rechts ab und wechselt dabei zwischen einer endlichen Anzahl von Zuständen. Darüber hinaus kann der KA in jedem Schritt eine beliebige Menge von Symbolen im Keller ablegen (push); von diesen Symbolen kann in jedem Schritt nur das oberste gelesen und entfernt werden (pop). Entsprechend wird durch eine KA-Transition ein Tupel aus Zustand, Eingabesymbol (gelesen vom Eingabeband) und Kellersymbol (oberstes Symbol des Kellerspeichers, 'pop') abgebildet auf einen Folgezustand und eine Sequenz von Symbolen, die in den Keller geschrieben werden ('push'). Eine Eingabe wird vom KA akzeptiert, falls er sich in einem Endzustand befindet, nachdem die komplette Eingabe verarbeitet wurde.

Vorgehensweise im XWizard:

  • Ein Skript wird mit pda: begonnen (für engl. push-down automaton), um anzuzeigen, dass es sich um einen KA handelt.
  • Das Verhalten des KA wird definiert durch eine Liste von Transitionen, von denen jede einzelne definiert ist als: (s0, a, b) => (s1, ab); (mit der Bedeutung: Wenn in Zustand s0 a vom Eingabeband gelesen wird und b vom Kellerspeicher, dann wechsle in Zustand s1 und schreibe ab in den Keller; da b vorher aus dem Keller entnommen wurde ('pop'), bedeutet das in diesem Fall, dass b wieder zurück gelegt wird und a darauf, sodass nun ein Zeichen mehr im Keller liegt, nämlich a, und zwar ganz oben).
  • Die Ausgabe zu einem KA-Skript besteht aus einer Sequenz (bzw. im nicht-deterministischen Fall aus einem Baum), worin die Berechnungsschritte für ein gegebenes Eingabewort dargestellt werden.
  • Das Eingabewort (im deterministischen Fall sind auch mehrere durch Komma getrennte erlaubt) wird im Deklarations-Bereich als inputs spezifiziert (klicke auf den grauen Konversions-Button   skript formatieren   oder   deklarationen hinzufügen  , um den Deklarations-Bereich zum Skript hinzuzufügen).
  • Der Anfangszustand s0, die Menge der Endzustände F und das spezielle Kellersymbol (das den 'Boden' des Kellers markiert) kSymb werden ebenfalls im Deklarations-Bereich festgelegt.
  • Durch klicken auf   zeige definition (latex)   wird der Latex-Modus aktiviert, der die Definition des KA anzeigt.
  • Für einen deterministischen KA kann mit dem Button   zeige berechnungsschritte (latex)   eine übersichtlichere Darstellung der Berechnungsfolge im Latex-Modus angezeigt werden.

Konversions-
methoden
Für Lehrende Erzeuge Aufgabe aus Skript...
X

Erzeuge ein Aufgaben-Skript aus diesem Skript. Bitte Parameter eingeben:

arg0: (String: Eine kurze Beschreibung oder einen Titel für die Aufgabe.)
arg1: (String: Eine lange Beschreibung der Aufgabe ein (HTML erlaubt).)
arg2: (String: Optional kann hier ein Lösungs-String für die Aufgabe angegeben werden.)
arg3: (String: Optionaler Belohnungscode, den der Benutzer durch das Lösen der Aufgabe verdienen kann.)
arg4: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Methodenname.)
arg5: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Skript-Klasse.)
arg6: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Zielklasse.)
arg7: (String: Optionaler Erklärungstext, der zusammen mit der Lösung angezeigt wird.)
arg8: (boolean: Auf true gesetzt wird die Verschlüsselung der Aufgabe - nicht des gesamten Skripts - veranlasst.)
arg9: (boolean: Auf true gesetzt wird die Verschlüsselung des gesamten Skripts veranlasst.)

Debuggen Schrittweise Script-Evaluation...
X

Erzeugt eine Animation der Expansion dieses Skripts zum Debuggen. (Es gibt nichts zu expandieren.) Bitte Parameter eingeben:

arg0: (Boolean: Auf true gesetzt, werden auch die in jedem Schritt verfügbaren Preprozessoren angezeigt.)

Beispiel:

→ Draw!




Zusammenfassen/Auseinanderziehen von Regeln: Skripte dieses Typs basieren auf sogenannten Regeln, etwa: X => Y; Regeln können über den Button   skript formatieren   (oder von Hand) folgendermaßen zusammengefasst werden:

A => B;
A => C;
A => D;
wird zu:
A => B | C | D;

...und ebenso:

A => D;
B => D;
C => D;
wird zu:
A | B | C => D;

...und sogar:

A => C;
A => D;
B => C;
B => D;
wird zu:
A | B => C | D;

Zusammengefasste und auseinandergezogene Regeln haben denselben Informationsgehalt, sie sind also in der oben gezeigten Weise austauschbar.

Hilfe zu 'Turingmaschine'

Der Begriff Turingmaschine (TM) bezeichnet ein wesentliches Automatenmodell der theoretischen Informatik. Es handelt sich um eine hypothetische Maschine, die, nach Regeln aus einer vorgegebenen Menge von Transitionen, Symbole auf einem eindimensionalen Band lesen und editieren kann. Von der Idee her stellt sie einen erweiterten endlichen Automaten dar, mit den folgenden Unterschieden:

  • Das Band ist sowohl nach links als auch nach rechts unbegrenzt (Ausnahmen stellen beschränkte Turingmaschinen dar, von denen die wichtigsten einseitig und linear beschränkte Turingmaschinen sind). Es enthält zu Beginn das Eingabewort, das von einer unendlichen Folge von Leerzeichen * auf jeder Seite umgeben ist. Beispiel: ...****abaabaabb****...
  • Der Kopf kann die Symbole auf dem Band einlesen und verändern, d.h. ein gelesenes Symbol durch ein anderes ersetzen. Er wird daher als Lese-/Schreibkopf bezeichnet.
  • Der Lese-/Schreibkopf kann sich in beide Richtungen bewegen (jew. ein Feld pro Berechnungsschritt) oder seine Position beibehalten.
  • Die Transitionsfunktion ist nicht total, sondern partiell definiert, d.h. dass es Zustände geben kann, bei denen für bestimmte Bandsymbole kein Folgezustand definiert ist. In diesem Fall (und nur dann) hält die TM.
Die TM wird als Formalismus zur Definition von berechenbaren Funktionen genutzt. Dabei nennt man den Prozess, den eine TM durch Transitionswechsel bis zum (potentiellen) Halten durchläuft, Rechnung. Die von der TM berechnete Funktion ist definiert als die Abbildung von dem zu Beginn der Rechnung auf dem Band stehenden Eingabewort auf das Wort, das nach dem Anhalten auf dem Band steht, d.h. das Wort, das während des Berechnungsprozesses generiert wurde. Eine Funktion wird genau dann als (Turing-) berechenbar bezeichnet, wenn es eine TM gibt, die sie berechnet. Darüber hinaus bezeichnet man all jene Eingabewörter als von einer TM akzeptiert, bei deren Eingabe sie in einem Endzustand anhält. Die Menge dieser Wörter wird als Sprache der TM bezeichnet. Da nicht alle Turingmaschinen für alle möglichen Eingabewörter anhalten, können die von ihnen definierten Funktionen partiell sein. Trotz ihres einfachen Aufbaus können Turingmaschinen jedes Programm, das auf irgendeinem üblichen Computer läuft, simulieren (also dieselbe Funktion berechnen wie das Programm).

Eine TM ist nichtdeterministisch, wenn für einen Zustand und ein bestimmtes Eingabesymbol mehr als eine mögliche Transition definiert ist. In diesem Fall führt die TM alle Möglichkeiten parallel aus, was zu einem Berechnungsbaum führt (statt einer Berechnungsfolge, wie im deterministischen Fall). Eine nichtdeterministische TM akzeptiert alle Eingabewörter, die zu einem Berechnungsbaum führen, bei dem mindestens ein Ast in einen Endzustand mündet. Zu beachten ist, dass nichtdeterministische Turingmaschinen ein rein theoretisches Konzept sind, das in der realen Welt nicht realisiert werden kann. Weitere Einzelheiten bezüglich Turingmaschinen können → hier nachgelesen werden.

Vorgehensweise im XWizard:

  • Ein Skript wird mit turing: begonnen, um anzuzeigen, dass es sich um eine TM handelt.
  • Anstatt eine Tabelle zu verwenden, erwartet der XWizard eine Liste von Transitionen der Form: (s0, a) => (s1, b, R); (Bedeutung: Wenn in Zustand s0 das Zeichen a vom Band gelesen wird, wechsle in Zustand s1, schreibe das Zeichen b an die momentane Position des Lese-/Schreibkopfes auf dem Band und bewege den Lese-/Schreibkopf einen Schritt nach rechts; auch erlaubt: L für links und N für neutral, d.h. keine Änderung der Position).
  • Die Liste der Zustände sowie die Symbole des Eingabe- und des Bandalphabets werden nicht explizit angegeben. Beim Einlesen einer Transition wird angenommen, dass die angegebenen Zustände (s0, s1 im obigen Beispiel) sowie die Bandsymbole (a, b im obigen Beispiel) zur TM gehören.
  • Der Anfangszustand (s0), die Liste der Endzustände (F) und das Leerzeichen (*) müssen im Deklarations-Bereich definiert werden (klicke auf den grauen Konversions-Button   skript formatieren   oder   deklarationen hinzufügen  , um den Deklarations-Bereich zum Skript hinzuzufügen).
  • Die Ausgabe einer TM besteht aus einer Folge von Bandzuständen, die den Verlauf der Berechnung für ein gegebenes Eingabewort repräsentieren. Dieses Eingabewort muss ebenfalls im Deklarations-Bereich angegeben werden. Zu diesem Zweck kann die Variable inputs mit einer (oder mehreren durch Kommas getrennten) Zeichenkette(n) belegt werden. Im Falle mehrerer Eingabewörter werden mehrere Berechnungsfolgen nebeneinander angezeigt. Es ist zu beachten, dass für nichtdeterministische TM nur ein Eingabewort erlaubt ist (der Übersichtlichkeit halber, da die Ausgabe dann ein Berechnungsbaum ist).
  • Da Turingmaschinen theoretisch unendlich lange laufen können, legt die Variable runStepsScript eine Obergrenze dafür fest, wie viele Berechnungsschritte simuliert werden sollen.
  • Wird die Variable shortTrace auf 'true' gesetzt, verbirgt der XWizard Berechnungsschritte, die keine Bandänderung zur Folge haben.
  • Neben der Standardausgabe stehen für ein TM-Skript Methoden zur Konversion in Latex Skripte zur Verfügung. So kann die Transitionstafel oder eine (anschaulichere) Darstellung der Berechnungsfolge angezeigt werden.
  • Außerdem kann durch Klicken auf   zufälliger busy-beaver   eine zufällige TM erstellt werden. In Abhängigkeit von einer anzugebenden Anzahl |S| an Zuständen und einer ebenfalls anzugebenden Anzahl t an Wiederholungen erstellt der Algorithmus t zufällige Turingmaschinen mit jew. |S| Zuständen bei zugehörigem Eingabewort *. Das ausgegebene Skript ist das für diejenige der t Turingmaschinen, deren berechnetes Ausgabe-Wort die meisten '1en' enthält, d.h. die 'fleißigste' aller erstellen Maschinen. Vgl. die Definition des → Fleißigen Bibers.

Konversions-
methoden
Konversion in Zufälliger Busy-Beaver...
X

Erzeuge eine neue, zufällige Turingmaschine, die einen 'Busy-Beaver' approximiert Bitte Parameter eingeben:

arg0: (int: Die Anzahl an Zuständen, die die einen → Busy-Beaver annähernde Turingmaschine haben soll.)
arg1: (int: Einen Busy-Beaver für eine beliebige Anzahl an Zuständen anzugeben, ist unmöglich, da das ein unberechenbares Problem ist. Daher generiert diese Methode eine gewisse Anzahl an zufälligen Turingmaschinen und gibt diejenige zurück, die die meisten Einsen auf das Band schreibt, also einem Busy-Beaver am nächsten ist. Die Anzahl der zu testenden Turingmaschinen wird hier angegeben.)

Für Lehrende Erzeuge Aufgabe aus Skript...
X

Erzeuge ein Aufgaben-Skript aus diesem Skript. Bitte Parameter eingeben:

arg0: (String: Eine kurze Beschreibung oder einen Titel für die Aufgabe.)
arg1: (String: Eine lange Beschreibung der Aufgabe ein (HTML erlaubt).)
arg2: (String: Optional kann hier ein Lösungs-String für die Aufgabe angegeben werden.)
arg3: (String: Optionaler Belohnungscode, den der Benutzer durch das Lösen der Aufgabe verdienen kann.)
arg4: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Methodenname.)
arg5: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Skript-Klasse.)
arg6: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Zielklasse.)
arg7: (String: Optionaler Erklärungstext, der zusammen mit der Lösung angezeigt wird.)
arg8: (boolean: Auf true gesetzt wird die Verschlüsselung der Aufgabe - nicht des gesamten Skripts - veranlasst.)
arg9: (boolean: Auf true gesetzt wird die Verschlüsselung des gesamten Skripts veranlasst.)

Debuggen Schrittweise Script-Evaluation...
X

Erzeugt eine Animation der Expansion dieses Skripts zum Debuggen. (Es gibt nichts zu expandieren.) Bitte Parameter eingeben:

arg0: (Boolean: Auf true gesetzt, werden auch die in jedem Schritt verfügbaren Preprozessoren angezeigt.)

Beispiel:

→ Draw!




Zusammenfassen/Auseinanderziehen von Regeln: Skripte dieses Typs basieren auf sogenannten Regeln, etwa: X => Y; Regeln können über den Button   skript formatieren   (oder von Hand) folgendermaßen zusammengefasst werden:

A => B;
A => C;
A => D;
wird zu:
A => B | C | D;

...und ebenso:

A => D;
B => D;
C => D;
wird zu:
A | B | C => D;

...und sogar:

A => C;
A => D;
B => C;
B => D;
wird zu:
A | B => C | D;

Zusammengefasste und auseinandergezogene Regeln haben denselben Informationsgehalt, sie sind also in der oben gezeigten Weise austauschbar.

Hilfe zu 'Grammatik'

In der Theorie der formalen Sprachen (die sowohl in der theoretischen Informatik als auch in der Linguistik betrachtet wird), versteht man unter einer Chomsky Grammatik, formalen Grammatik oder einfach Grammatik im Grunde eine Menge von Produktionsregeln für Zeichenketten, d.h., Symbolsequenzen. Die Regeln beschreiben, wie über einem gegebenen Alphabet gültige Zeichenketten abgeleitet werden können, in Unterscheidung zur Menge der übrigen, nicht ableitbaren Zeichenketten, die als ungültig bezeichnet werden. Die Menge gültiger Zeichenketten heißt (formale) Sprache der Grammatik. Grammatiken werden in der Regel als erzeugende Systeme für Sprachen bezeichnet, weil sie definieren, wie aus einer Anfangszeichenkette die gültigen Zeichenketten abgeleitet bzw. bildhaft 'produziert' werden.

Wort-Erzeugung: Die Produktionen einer Grammatik definieren eine Menge von modifizierenden Operationen auf Zeichenketten, wie etwa Zeichenkette => andere-Zeichenkette, in Verbindung mit einem Startsymbol S. Beginnend mit der Menge {S} (die nur das Startsymbol enthält), werden zu dieser Menge alle Zeichenketten hinzugefügt, die erzeugt werden können, indem bei einer bereits enthaltenen Zeichenkette ein Teil, der der linken Seite einer Produktion entspricht, durch deren rechten Teil ersetzt wird. Die Sprache der Grammatik ist definiert als diejenige Teilmenge dieser konstruierten Menge, deren Zeichenketten nur terminale Wörter darstellen, d.h. Wörter, die nur Zeichen des zugrundeliegenden Alphabets enthalten. Dieses wird als Menge T der Terminalsymbole bezeichnet. Die übrigen Symbole werden als Menge N der Nichtterminalsymbole bezeichnet.

Grammatiken können auch als Basis für Erkenner verwendet werden, d.h. Programme, die feststellen, ob eine gegebene Zeichenkette zur Sprache einer Grammatik gehört oder nicht. Zu diesem Zweck wird die Grammatik von einem Automaten verarbeitet, der eigentlich zu den erkennenden Formalismen in Bezug auf formale Sprachen gehört (in der Praxis handelt es sich um ein Computerprogramm, was wir in der Theorie aber durch einen Automaten modellieren). Wichtig ist hier zu verstehen, dass der Automat nicht zum Erkennen der jeweiligen Sprache einer bestimmten Grammatik konstruiert wird. Vielmehr handelt es sich um einen allgemeinen Automaten, der sowohl die Grammatik als auch das zu prüfende Wort einliest und daraus die Antwort auf die Frage berechnet, ob das Wort in der Sprache der Grammatik ist oder nicht. Zusätzlich zu diesem bloßen Erkennungsprozess kann eine Grammatik auch dazu verwendet werden, eine gegebene Zeichenkette zu parsen, falls sie zur Sprache der Grammatik gehört. Das Parsen liefert Informationen dazu, wie die Zeichenkette in Bezug zur Grammatik strukturiert ist, wie sie also durch die Grammatik abgeleitet wird. Grammatiken vom Chomsky-Typ 2 können effizienet geparst werden (z.B. mittels eines → Earley-Parsers, der auch vom XWizard genutzt wird). Als Ergebnis ergibt sich ein → Syntaxbaum (auch Parsebaum oder Ableitungsbaum). Aufgrund dieser Eigenschaften sind Grammatiken des Typs 2 besonders als Basis für Programmiersprachen geeignet. Ein 'Wort' ist in diesem Zusammenhang ein zu kompilierendes Programm in der jeweiligen Sprache (z.B. Java). Da zu Java (und praktisch jeder anderen modernen Programmiersprache) eine Grammatik gehört, kann durch einen Parser zunächst geprüft werden, ob das Wort ein gültiges Programm darstellt (Erkennung). Sowohl im positiven Fall als auch im negativen können dann durch die Parsing-Informationen weitergehende Informationen über die Struktur des Programms abgeleitet werden. (Zum gesamten Kompilierungsprozess gehören allerdings noch weitere Komponenten, z.B. Lexer, Tokenizer usw.) Weitere Einzelheiten bezüglich Grammatiken können → hier nachgelesen werden.

Vorgehensweise im XWizard:

  • Ein Skript wird mit grammar: begonnen, um anzuzeigen, dass es sich um eine formale Grammatik handelt. Es wird zunächst ein Gesamtbaum dargestellt, d.h. alle Wörter, die von S ausgehend bis zu einer bestimmten Tiefe erzeugt werden können. Durch Hinzufügen von parse(a, a, b, b, a, b)--0 zur Preambel (direkt vor dem Doppelpunkt), wird der Parse-Modus aktiviert, der den (bzw. einen) Syntaxbaum für das angegebene Wort a, a, b, b, a, b zeigt.
  • Um zwischen den beiden Modi zu wechseln, können auch die Buttons   gesamtbaum   und   parse einzelnes wort   verwendet werden.
  • Falls ein Wort auf verschiedene Arten geparst werden kann, kann zwischen den jeweiligen Syntaxbäumen durch Klicken auf den Button   durchlaufe...   gewechselt werden oder indem man die 0 in --0 durch eine andere Zahl ersetzt.
  • Es ist zu beachten, dass alle Syntaxbäume berechnet werden, nicht nur die, deren Wurzel das Startsymbol ist. Nur die letzteren stellen allerdings gültige Ableitungen des Wortes durch die Grammatik dar.
  • Die Produktionen der Grammatik werden in der Form A, S => b, A, A, c angegeben.
  • In Grammatik-Skripten kann ein Symbol aus mehreren Zeichen bestehen, daher werden Symbole durch Kommas voneinander getrennt.
  • Sowohl die linke als auch die rechte Seite einer Produktionsregel kann aus mehr als einem Symbol bestehen (vgl. Chomsky-Hierarchie).
  • Nach Konvention werden Großbuchstaben in der Regel für Nonterminalsymbole verwendet, Kleinbuchstaben für Terminalsymbole. Trotzdem können sowohl Nonterminal- als auch Terminalsymbole und das Startsymbol explizit im Deklarations-Bereich als N, T, S (klicke auf den grauen Konversions-Button   skript formatieren   oder   deklarationen hinzufügen  , um den Deklarations-Bereich zum Skript hinzuzufügen) angegeben werden (auch entgegen der beschriebenen Konvention, falls gewünscht).
  • Im regulären Modus können die Variablen maxdepth, maxLengthWords, cutNonTerminalBranches, cutTerminalDoubleBranches verwendet werden, um die Größe des erzeugten Baumes zu beschränken. Die beiden ersten legen eine maximale Baum-Tiefe und Wortlänge fest. Die beiden letzten verbergen jeweils alle Zweige zu nichtterminalen Wörtern und zu terminalen Wörtern, die bereits durch einen anderen Zweig erzeugt wurden.
  • Durch Konversionsmethoden kann die Grammatik   epsilon-frei  gemacht, in   chomsky nf  ,   greibach nf   oder (bei Typ-1-Grammatiken)   kuroda nf   überführt, oder durch den Button   randomize   durch eine neue, zufällig generierte (Typ-2-) Grammatik ersetzt werden.
  • Ein äquivalenter Kellerautomat kann erstellt werden, indem auf   kellerautomat   geklickt wird.
  • Durch Klicken auf   anzeigemodus   können verschiedene Sichten auf die Grammatik angezeigt werden. Dazu gehört die Grammatikdefinition, ein Ableitungsbaum und die Ableitungen eines zu parsenden Wortes.
  • Wird multiLetterSymbolsHaveIndex=true gesetzt, werden Symbole mit mehr als einem Zeichen so angezeigt, dass alle Zeichen nach dem Ersten tiefergestellt sind.
Es ist zu beachten, dass der Parse-Modus und die meisten Konversionsmethoden eine Grammatik vom Typ 2 erfordern. Es existieren keine Syntaxbäume für Grammatiken, die nicht vom Typ 2 sind, und die Entscheidung, ob ein Wort zur Sprache einer solchen Grammatik gehört, ist mindestens NP-schwer; Auch die Chomsky- und Greibach-Normalformen gibt es nicht bei Nicht-Typ-2-Grammatiken, und sie epsilon-frei zu machen ist schwieriger. In der Zukunft werden vielleicht weitere Konversionsmethoden für Nicht-Typ-2-Grammatiken implementiert. Die Kuroda-Normalform ist ein erster Anfang.

Konversions-
methoden
Konversion in Parse einzelnes Wort...
X

Füge zu parsendes Wort ins Skript ein und wechsle zur Parse-Baum-Sicht Bitte Parameter eingeben:

arg0: (String: Gib ein Wort ein, für das der Parsebaum erzeugt werden soll. Falls es Symbole enthalten soll, die aus mehreren Buchstaben bestehen (etwa S'), müssen alle Symbole durch Kommas getrennt werden.)

Für Lehrende Erzeuge Aufgabe aus Skript...
X

Erzeuge ein Aufgaben-Skript aus diesem Skript. Bitte Parameter eingeben:

arg0: (String: Eine kurze Beschreibung oder einen Titel für die Aufgabe.)
arg1: (String: Eine lange Beschreibung der Aufgabe ein (HTML erlaubt).)
arg2: (String: Optional kann hier ein Lösungs-String für die Aufgabe angegeben werden.)
arg3: (String: Optionaler Belohnungscode, den der Benutzer durch das Lösen der Aufgabe verdienen kann.)
arg4: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Methodenname.)
arg5: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Skript-Klasse.)
arg6: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Zielklasse.)
arg7: (String: Optionaler Erklärungstext, der zusammen mit der Lösung angezeigt wird.)
arg8: (boolean: Auf true gesetzt wird die Verschlüsselung der Aufgabe - nicht des gesamten Skripts - veranlasst.)
arg9: (boolean: Auf true gesetzt wird die Verschlüsselung des gesamten Skripts veranlasst.)

Debuggen Schrittweise Script-Evaluation...
X

Erzeugt eine Animation der Expansion dieses Skripts zum Debuggen. (Es gibt nichts zu expandieren.) Bitte Parameter eingeben:

arg0: (Boolean: Auf true gesetzt, werden auch die in jedem Schritt verfügbaren Preprozessoren angezeigt.)

Beispiel:

→ Draw!




Zusammenfassen/Auseinanderziehen von Regeln: Skripte dieses Typs basieren auf sogenannten Regeln, etwa: X => Y; Regeln können über den Button   skript formatieren   (oder von Hand) folgendermaßen zusammengefasst werden:

A => B;
A => C;
A => D;
wird zu:
A => B | C | D;

...und ebenso:

A => D;
B => D;
C => D;
wird zu:
A | B | C => D;

...und sogar:

A => C;
A => D;
B => C;
B => D;
wird zu:
A | B => C | D;

Zusammengefasste und auseinandergezogene Regeln haben denselben Informationsgehalt, sie sind also in der oben gezeigten Weise austauschbar.

Hilfe zu 'Regulärer-Ausdruck'

In der theoretischen Informatik und der Theorie formaler Sprachen bezeichnet der Begriff Regulärer Ausdruck (RA; engl. regular expression, regex) eine operationelle Methode um eine formale Sprache zu definieren. Für ein Alphabet E definiert ein RA α (mit Hilfe einer Menge von Basisoperationen auf Mengen), wie Zeichen aus E zu Zeichenketten, d.h. zu Wörtern der Sprache L(α), kombiniert werden können. In diesem Sinne ist α ein gültiger RA, wenn

  • α = oder α = e für e ∈ E oder
  • α = (α1 + α2) (Vereinigung) oder
  • α = (α1 · α2) (Konkatenation) oder
  • α = (α1)* (Iteration or 'Kleenesche Hülle')
für gültige RA α1, α2. Die Sprache eines RA wird durch rekursive Auswertung des oben definierten Schemas wie folgt konstruiert:
  • L() = , L(e) = {e},
  • L((α1 + α2)) = L(α1) ∪ L(α2)
  • L((α1 · α2)) = L(α1) L(α2) wobei L1 L2 = {w1w2 | w1 ∈ L1, w2 ∈ L2}, und
  • L((α1)*) = i ∈ 0 L(α1)i.
Beispielsweise ist ((a · b))* ein regulärer Ausdruck über dem Alphabet E = {a, b}, der die Sprache {λ, ab, abab, ababab, ...} definiert. Klammern können wie üblich weggelassen werden, solange ein RA eindeutig über die Operatorengewichtung * vor · vor + ausgewertet werden kann. Außerdem wird · in der Regel nicht explizit hingeschrieben. Damit kann der oben genannte RA auch umgeschrieben werden in (ab)*. Beachten Sie, dass der Spezialfall des leeren Wortes λ per Definition schon durch den RA * abgedeckt ist (trotzdem erlauben manche Autoren in der Literatur auch λ explizit als RA mit der Bedeutung L(λ) = {λ}).

Die Sprachen, die durch RA definiert werden können, sind genau dieselben, die von endlichen Automaten erkannt bzw. von rechtslinearen Grammatiken generiert werden können. Es gibt auch Algorithmen, mittels derer für jeden RA ein äquivalenter endlicher Automat konstruiert werden kann und umgekehrt (dasselbe gilt für rechtslineare Grammatiken).

In der Praxis werden RA hauptsächlich zur Mustererkennung bei Aufgaben vom Typ 'Finden und Ersetzen' verwendet. Sie finden bspw. breite Anwendung in den UNIX-Werkzeugen ed, einem Editor, und grep (global regular expression print), einem Filterwerkzeug, aber selbstverständlich auch in den meisten modernen Programmiersprachen, wie Java, C# etc. RA haben sich als höchst nützlich für Anwendungen dieser Art erwiesen, und im Lauf der Zeit sind die oben definierten Basisoperationen zur Vereinfachung der Arbeit noch erheblich erweitert worden. Der XWizard unterstützt jedoch nur die Basisoperationen.

Weitere Einzelheiten bezüglich regulärer Ausdrücke, insbesondere auch Hinweise zum praktischen Gebrauch, können → hier nachgelesen werden.

Vorgehensweise im XWizard:

  • Ein Skript für einen RA beginnt mit regex:
  • Die Skripteingabe ist ein regulärer Ausdruck, der in der üblichen Weise abgekürzt werden darf.
  • Alle Kleinbuchstaben (a, b, c, ...) und Ziffern (0, 1, 2, ...) sind Teil des Terminalalphabets.
  • Vereinigung ist kodiert als +, Konkatenation als . (kann weggelassen werden), die Kleene'sche Stern-Operation als *.
  • O (der Großbuchstabe, nicht die Zahl) ist die leere Menge , O* (entsprechend) das leere Wort λ.
  • Die Ausgabe wird automatisch durch einige Standard-Operationen vereinfacht. Um auch das Skript zu vereinfachen, klicke auf   vereinfache (ein bisschen)  .
  • Es ist zu beachten, dass die Minimierung eines RA PSPACE-vollständig ist, alle Vereinfachungen sind also nur Operationen, die mit 'gesundem Menschenverstand' ersichtlich sind und den RA oft nur rudimentär vereinfachen.

Konversions-
methoden
Für Lehrende Erzeuge Aufgabe aus Skript...
X

Erzeuge ein Aufgaben-Skript aus diesem Skript. Bitte Parameter eingeben:

arg0: (String: Eine kurze Beschreibung oder einen Titel für die Aufgabe.)
arg1: (String: Eine lange Beschreibung der Aufgabe ein (HTML erlaubt).)
arg2: (String: Optional kann hier ein Lösungs-String für die Aufgabe angegeben werden.)
arg3: (String: Optionaler Belohnungscode, den der Benutzer durch das Lösen der Aufgabe verdienen kann.)
arg4: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Methodenname.)
arg5: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Skript-Klasse.)
arg6: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Zielklasse.)
arg7: (String: Optionaler Erklärungstext, der zusammen mit der Lösung angezeigt wird.)
arg8: (boolean: Auf true gesetzt wird die Verschlüsselung der Aufgabe - nicht des gesamten Skripts - veranlasst.)
arg9: (boolean: Auf true gesetzt wird die Verschlüsselung des gesamten Skripts veranlasst.)

Debuggen Schrittweise Script-Evaluation...
X

Erzeugt eine Animation der Expansion dieses Skripts zum Debuggen. (Es gibt nichts zu expandieren.) Bitte Parameter eingeben:

arg0: (Boolean: Auf true gesetzt, werden auch die in jedem Schritt verfügbaren Preprozessoren angezeigt.)

Beispiel:

→ Draw!

Hilfe zu '2-3-4-Baum'

Ein 2-3-4-Baum ist eine sich selbst balancierende Datenstruktur. Jeder Knoten besitzt entweder zwei, drei oder vier Kindknoten. Ein Zwei-Knoten besitzt ein Datenelement, ein drei Knoten zwei Elemente und ein Vier-Knoten drei Elemente. Alle Blätter besitzen die gleiche Tiefe. Für weitere Informationen siehe → Wikipedia

Vorgehensweise im XWizard: Der Baum kann über zwei verschiedene Wege definiert werden. In der simplen Variante kannst du einfach ein Folge an Elementen eingeben, die durch Leerzeichen getrennt sind. Diese Elemente werden nacheinander in einen leeren Baum eingefügt, so dass er Anordnung von links nach rechts ihre Einfügereihenfolge in den Baum angibt. Der simple Modus wird aktiviert in dem simple- dem Präfix tree234: vorangestellt wird.

Der Baum kann auch über eine Skriptsprache definiert werden. Bitte berücksichtigte, dass die Implementierung nicht überprüft ob dein Skript einen korrekten Baum definiert, obwohl eine rudimentäre Prüfung auf Korrektheit stattfindet. (Das Programm überprüft bspw. bisher noch nicht, ob der Baum balanciert ist oder ob die Ordnung der Knoten korrekt ist. Ein Knoten wir definiert, in dem all seine Werte in eckige Klammern geschrieben werden und durch Kommas getrennt werden. Eine Eltern-Kind Beziehung zwischen zwei Knoten kann durch die folgende Syntax hergestellt werden: [p1] => [c1,c2];. Es ist möglich mehrere Kinder in der gleichen Regel zu definieren, in dem die Kinder durch einen senkrechten Strich getrennt werden, also [p1] => [c1,c2]|[c3];

Du kannst entweder ganze Zahlen, reelle Zahlen oder Zeichenketten in diesem Baum speichern. Du kannst den Typ der Werte, die gespeichert werden, über die Variable type ändern. Wähle entweder integer für ganze Zahlen, real für reelle Zahlen, oder string für Buchstaben oder Zeichenketten.




Zusammenfassen/Auseinanderziehen von Regeln: Skripte dieses Typs basieren auf sogenannten Regeln, etwa: X => Y; Regeln können über den Button   skript formatieren   (oder von Hand) folgendermaßen zusammengefasst werden:

A => B;
A => C;
A => D;
wird zu:
A => B | C | D;

...und ebenso:

A => D;
B => D;
C => D;
wird zu:
A | B | C => D;

...und sogar:

A => C;
A => D;
B => C;
B => D;
wird zu:
A | B => C | D;

Zusammengefasste und auseinandergezogene Regeln haben denselben Informationsgehalt, sie sind also in der oben gezeigten Weise austauschbar.

Hilfe zu 'Rot-Schwarz-Baum'

Ein Rot-Schwarz-Baum ist ein sich selbst balancierender binärer Suchbaum. Die selbst-balancierende Eigenschaft dieses Baums garantiert, dass Such-, Einfüge-, Lösch- (und Rebalancierungsoperationen) immer in der Zeit O(log n) ausgeführt werden, wobei n der Größe des Baums entspricht. Ein Rot-Schwarz-Baum unterscheidet zwischen roten und schwarzen Knoten (durch rote gepunktete und schwarze durchgezogene Linien in der PDF). Für weitere Informationen, siehe → Wikipedia.

Vorgehensweise im XWizard: Der Baum kann über zwei verschiedene Wege definiert werden. In der simplen Variante kannst du einfach ein Folge an Elementen eingeben, die durch Leerzeichen getrennt sind. Diese Elemente werden nacheinander in einen leeren Baum eingefügt, so dass er Anordnung von links nach rechts ihre Einfügereihenfolge in den Baum angibt. Der simple Modus wird aktiviert in dem simple- dem Präfix redblack: vorangestellt wird.

Der Baum kann auch über eine Skriptsprache definiert werden. Bitte berücksichtigte, dass die Implementierung nicht überprüft ob dein Skript einen korrekten Baum definiert, obwohl eine rudimentäre Prüfung auf Korrektheit stattfindet. (Das Programm überprüft bspw. bisher noch nicht, ob der Baum balanciert ist oder ob die Ordnung der Knoten korrekt ist. Nutze die die Syntax p => c um festzulegen, dass 'p' Elternknoten von 'c' ist. p und c sind Platzhalter für Werte, die du im Baum speichern möchtest. Um einen Knoten als rot zu deklarieren, füge den Präfix r: zu all seinen Vorkommnissen im Skript hinzu. Du kann den linken und rechten Kindknoten in einer Zeile definieren, in dem du die Werte der beiden Kinder mit einem senkrechten Strich trennst, also p => c1|c2

Du kannst entweder ganze Zahlen, reelle Zahlen oder Zeichenketten in diesem Baum speichern. Du kannst den Typ der Werte, die gespeichert werden, über die Variable type ändern. Wähle entweder integer für ganze Zahlen, real für reelle Zahlen, oder string für Buchstaben oder Zeichenketten.




Zusammenfassen/Auseinanderziehen von Regeln: Skripte dieses Typs basieren auf sogenannten Regeln, etwa: X => Y; Regeln können über den Button   skript formatieren   (oder von Hand) folgendermaßen zusammengefasst werden:

A => B;
A => C;
A => D;
wird zu:
A => B | C | D;

...und ebenso:

A => D;
B => D;
C => D;
wird zu:
A | B | C => D;

...und sogar:

A => C;
A => D;
B => C;
B => D;
wird zu:
A | B => C | D;

Zusammengefasste und auseinandergezogene Regeln haben denselben Informationsgehalt, sie sind also in der oben gezeigten Weise austauschbar.

Hilfe zu 'BDD'

Binary decision diagrams (BDDs) werden verwendet, um boolesche Funktionen in komprimierter Form darzustellen. Sie sind normalerweise effizienter als andere Darstellungsformen, wie z.B. Wahrheitstabellen oder Normalformen boolescher Ausdrücke (sowohl bezüglich des benötigten Speicherplatzes, als auch bezüglich der Berechnungszeit für ein gegebenes Tupel boolescher Eingabewerte). Im Gegensatz zu anderen Darstellungsformen können Operationen direkt mit der komprimierten Darstellung ausgeführt werden, also ohne sie vorher umwandeln zu müssen. BDDs werden aufsteigend von den Blättern zur Wurzel hin konstruiert, wie → hier beschrieben.

Vorgehensweise im XWizard:

  • Schreibe eine Reihe von 0en und 1en in der Reihenfolge wie sie in einer Standard-Wahrheitstabelle der gewünschten Funktion auftauchen würden, um ein BDD zu definieren.
  • Wenn die Länge nicht 2n für irgendein n ist, werden 0en am Ende aufgefüllt.
  • Wenn zu einem Skript Deklarationen hinzugefügt werden (klicke auf den grauen Konversions-Button   skript formatieren   oder   deklarationen hinzufügen  , um den Deklarations-Bereich zum Skript hinzuzufügen), kann die Anzahl der Konstruktionsschritte mittels der Variablen simplifySteps festgelegt werden (-1 um alle Schritte auszuführen).
  • Klicke auf   vereinfache schrittweise  , um den Wahrheitsbaum schrittweise zu vereinfachen. Dadurch wird der Wert der Variablen simplifySteps, wie oben beschrieben, um eins erhöht (alternativ kann das also auch von Hand gemacht werden).
  • Durch Klicken auf   wahrheitstabelle...   wird die Wahrheitstabelle generiert, die dem BDD zugrunde liegt.

Konversions-
methoden
Für Lehrende Erzeuge Aufgabe aus Skript...
X

Erzeuge ein Aufgaben-Skript aus diesem Skript. Bitte Parameter eingeben:

arg0: (String: Eine kurze Beschreibung oder einen Titel für die Aufgabe.)
arg1: (String: Eine lange Beschreibung der Aufgabe ein (HTML erlaubt).)
arg2: (String: Optional kann hier ein Lösungs-String für die Aufgabe angegeben werden.)
arg3: (String: Optionaler Belohnungscode, den der Benutzer durch das Lösen der Aufgabe verdienen kann.)
arg4: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Methodenname.)
arg5: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Skript-Klasse.)
arg6: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Zielklasse.)
arg7: (String: Optionaler Erklärungstext, der zusammen mit der Lösung angezeigt wird.)
arg8: (boolean: Auf true gesetzt wird die Verschlüsselung der Aufgabe - nicht des gesamten Skripts - veranlasst.)
arg9: (boolean: Auf true gesetzt wird die Verschlüsselung des gesamten Skripts veranlasst.)

Debuggen Schrittweise Script-Evaluation...
X

Erzeugt eine Animation der Expansion dieses Skripts zum Debuggen. (Es gibt nichts zu expandieren.) Bitte Parameter eingeben:

arg0: (Boolean: Auf true gesetzt, werden auch die in jedem Schritt verfügbaren Preprozessoren angezeigt.)

Beispiel:

→ Draw!

Hilfe zu 'Huffman-Code'

In der Informatik und der Informationstheorie ist eine Huffman-Kodierung ein bestimmter optimaler Präfix-Code, der häufig für verlustfreie Datenkompression verwendet wird. Die Huffman-Kodierung ordnet jedem zu kodierenden Zeichen ein Bit-Wort zu, so dass der resultierende Code die → Fano-Bedingung erfüllt (kein Codewort ist das Präfix eines anderen) und für eine gegebene Wahrscheinlichkeitsverteilung der Zeichen eine minimale Größe aufweist. Die Vorgehensweise, um einen solchen Code zu erstellen und zu verwenden, geht auf einen Algorithmus zurück, den David A. Huffman während seiner Zeit als Doktorand am MIT entwickelt hat. Weitere Einzelheiten über die Huffman-Kodierung können → hier nachgelesen werden.

Vorgehensweise im XWizard:

  • Gib einen beliebigen Text ein, der als Basis für die Berechnung des Huffman-Baums genommen werden soll.
  • Zu beachten ist, dass Leerzeichen und Zeilenumbrüche auch gezählt werden.
  • Die Ausgabe besteht aus einem Huffman-Baum. Ausgehend von der Wurzel bis zu den einzelnen Blättern stellt die Folge der Markierungen der besuchten Kanten das Codewort für das kodierte Zeichen (im jeweiligen Blatt) dar (die obere linke Ecke des jeweiligen Blattes enthält dieses Zeichen; die Auftrittswahrscheinlichkeit für einen gegebenen Text wird in der oberen rechten Ecke angezeigt, die Kodierung des Zeichens unten).
  • Es ist zu beachten, dass der Huffman-Baum in der Regel nicht eindeutig ist; inbesondere die Bezeichnung der Kanten mit 1 wenn sie von rechts nach links gezeichnet werden und mit 0 sonst (so wie es der XWizard macht) ist völlig willkürlich. Solange jeder Vater-Knoten (der kein Blatt ist) eine 0 und eine 1 Kante zu einem entsprechenden Kind-Knoten hat, sind alle Kombinationen erlaubt.
  • Mit der booleschen Variablen classicView (klicke auf den grauen Konversions-Button   skript formatieren   oder   deklarationen hinzufügen  , um den Deklarations-Bereich zum Skript hinzuzufügen) kann zwischen verschiedenen Ansichten gewechselt werden.

Konversions-
methoden
Für Lehrende Erzeuge Aufgabe aus Skript...
X

Erzeuge ein Aufgaben-Skript aus diesem Skript. Bitte Parameter eingeben:

arg0: (String: Eine kurze Beschreibung oder einen Titel für die Aufgabe.)
arg1: (String: Eine lange Beschreibung der Aufgabe ein (HTML erlaubt).)
arg2: (String: Optional kann hier ein Lösungs-String für die Aufgabe angegeben werden.)
arg3: (String: Optionaler Belohnungscode, den der Benutzer durch das Lösen der Aufgabe verdienen kann.)
arg4: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Methodenname.)
arg5: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Skript-Klasse.)
arg6: (String: Optionaler → Regulärer Ausdruck (Java) zum Einschränken der angezeigten Konversionsmethoden - Zielklasse.)
arg7: (String: Optionaler Erklärungstext, der zusammen mit der Lösung angezeigt wird.)
arg8: (boolean: Auf true gesetzt wird die Verschlüsselung der Aufgabe - nicht des gesamten Skripts - veranlasst.)
arg9: (boolean: Auf true gesetzt wird die Verschlüsselung des gesamten Skripts veranlasst.)

Debuggen Schrittweise Script-Evaluation...
X

Erzeugt eine Animation der Expansion dieses Skripts zum Debuggen. (Es gibt nichts zu expandieren.) Bitte Parameter eingeben:

arg0: (Boolean: Auf true gesetzt, werden auch die in jedem Schritt verfügbaren Preprozessoren angezeigt.)

Beispiel:

→ Draw!

Hilfe zu 'Schaltkreis'

Logische Schaltkreise sind bisher nur in einer rudimentären Version implementiert und haben wenig Funktionalität. Auch ist die Darstellung für komplexe Schaltkreise nicht schön - wir arbeiten daran. Ein logischer Schaltkreis wird definiert durch eine Liste von Verbindungen:
  • von einem Gatter X zum Eingang n eines anderen Gatters Y als:
    X => Y.n;
  • oder von einem Schaltungseingang I zum Eingang n eines Gatters Y als:
    I => Y.n;
  • oder von einem Gatter X zu einem Schaltungsausgang O als:
    X => O;
Undefinierte Elemente I,O werden jeweils als Schaltungseingang oder Schaltungsausgang behandelt. Die übrigen Elemente, d.h. Gatter, werden im Deklarationsbereich definiert, bspw.:
components = A:NOT, B:XOR-nnin, C:XOR, D:AND, E:AND, F:OR;
Soll ein Gatter mehr als zwei Eingänge haben, kann eine Sequenz aus n und i (vgl. B im Beispiel) für 'normale' bzw. 'invertierte' Eingänge angegeben werden.


Zusammenfassen/Auseinanderziehen von Regeln: Skripte dieses Typs basieren auf sogenannten Regeln, etwa: X => Y; Regeln können über den Button   skript formatieren   (oder von Hand) folgendermaßen zusammengefasst werden:

A => B;
A => C;
A => D;
wird zu:
A => B | C | D;

...und ebenso:

A => D;
B => D;
C => D;
wird zu:
A | B | C => D;

...und sogar:

A => C;
A => D;
B => C;
B => D;
wird zu:
A | B => C | D;

Zusammengefasste und auseinandergezogene Regeln haben denselben Informationsgehalt, sie sind also in der oben gezeigten Weise austauschbar.

Hilfe zu 'Zahlen'

LONG_TEST_G


XWizard documentation (see also → help pages):
XWizard 3_3.0 is the web version of → Very Fast PDF Generator. © Lukas König et al., 2007-2018 | → Contact
→ Empfohlen:

Neu und sehr gut!