qcoan Version 2.0 (Turingsimulator & Automatensimulator) | SourceCodes als tar.bz2, und als .zip now with GPLv3 | Windows Executable, ucrtbased.dll | Linux Compilate |
---|---|---|---|
CoAn LE Version 1.1 (Turingsimulator & Automatensimulator) | Windows Executable (update 19.03 2004) | ||
CoAn TLE Version 1.0 (Turingsimulator) | Executable | Doku. und Bsp. (Michael Leitner) | |
SHA512SUMS: software/SHA512SUMS.signed |
Bitte unterschreiben Sie die Contributor License Agreement, wenn Sie an der Entwicklung mitwirken wollen; sonst können wir Ihre Änderungen nicht in unsere über elstel.org verfügbare Version übernehmen.
Hinweis: Öffnen Sie Test2.atm für Beispiele. Wenn sich das Programm unter Windows nicht starten läßt kopieren Sie zusätzlich ucrtbased.dll in das coan-2.0-exe Verzeichnis.
Vollständiger Automatensimulator mit Simulation von endlichen Automaten, Kellerautomaten, Turingmaschinen und Maschinenschema
Motivation: qCoAn ist ein Programm zum Simulieren nicht-deterministischer Kellerautomaten und Turingmaschinen. Diese Maschinen werden in der theoretischen Informatik definiert. Endliche Automaten werden für reguläre Ausdrücke und Kellerautomaten bspw. zum Parsen von Programmiersprachen verwendet. Turingmaschinen finden als Modell der Berechenbarkeit Verwendung und um unbeschränkte oder kontextsensitive Grammatiken zu implementieren wie z.B. Ax → xA. Das Programm kann derzeit zur Modellierung, zum Design und für Lehrzwecke verwendet werden. Nichtsdestoweniger ist es geplant eine Konsolenversion von qcoan herauszubringen, die dann direkt zum Erkennen regulärer Ausdrücke und als Mini-Parser eingesetzt werden kann. Die Implementierung besteht aus drei Schichten, sodaß das Programm auch ohne grafischer Oberfläche kompiliert werden kann.
folgende Abkürzungen sind gebräuchlich: PDA - pusdown automaton (i.e. Kellerautomat), DFA - deterministic finite automaton (endlicher Automat, deterministisch), NFA - non-deterministic finite automaton (nichtdeterministischer endlicher Automat), NPDA non-deterministic pushdown automaton (nichtdeterministischer Kellerautomat), NDTM non-deterministic Turing Machine (nichtdeterministische Turingmaschine)
Die leere Menge wird mit dem Symbol “∅” angezeigt, kann aber einfach als Zeichenfolge ohne jedes Zeichen eingegeben werden. bspw. kann die Zeichenfolge “α≠∅//α” als “\alpha!=//\alpha” eingegeben werden. Die volle Zeichenfolge mit allen Zeichen läßt sich als das Komplement der leeren Zeichenmenge darstellen: “!=” Wenn es links vom Ungleichheitszeichen keine Variable gibt, an die zugewiesen werden kann, dann komplementiert der Ungleichheitsoperator einfach die Zeichenmenge rechts von ihm. Die leere Zeichenfolge als Gesamttext für einen Übergang bezeichnet einen Epsilonübergang.
Es gibt mehrschrittige Übergänge, bei denen mehrere Zeichen eines nach dem anderen gelesen werden: “a\+b\+c” wird übersetzt in “a⚬b⚬c”. Wenn die Ringe ausgelassen werden nimmt qcoan auch einen mehrschrittigen Übergang an. Wenn Sie einen Übergang mit einer Zeichenmenge, der nur ein einziges Zeichen einliest, haben wollen (also beispielsweise eines der Zeichen a,b,c), dann geben Sie “abc\+” oder “abc⚬” ein. Sobald Sie den Mengenabzugsoperator “\-” - “∖” oder den Zeichenbereichsoperator “a\..c” - “a…c” verwenden wird qcoan auch einen Übergang mit Zeichenmenge statt einem mehrschrittigen Übergang annehmen.
Wenn Sie schließlich mehrere Übergänge mit Variablen haben, die von einem Zustand ausgehen, dann vergessen Sie nicht auf den Mengenabzugsoperator um Mehrdeutigkeiten zu vermeiden: “α”, “β∖α”, “γ∖αβ”. Variablen in Kellerautomaten sind übergangslokal während Variablen in Turingmaschinen und Maschinenschemata global sind. Weiters verfügen alle Automaten über die Möglichkeit vor der Ausführung vordefinierte Variablen zu verwenden.