Turing- und Automatensimulator

CoAn - Compiler und Automaten Netzwerksimulator



Downloads:
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.


jetzt **neu** in Version 2.0: vollständig in C++/Qt für Linux und Windows, nichtdeterministische Turingmaschinen, mehrbuchstabige Übergänge und Übergänge mit Zeichenmengen für endliche Automaten, parameterisierte Maschinenschemata mit Hochzahlen für mehrmalige Wiederholung eines Automaten.

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 Maschinenschemata. Simulation von deterministischen und nicht deterministischen Automaten (alle gleichzeitig aktiven Zustände werden gelb angezeigt). Nichtdeterministische Stapelautomaten werden unter Anzeige aller möglichen Stapelinhalte zu einem bestimmten Aktivierungszustand simuliert. Mit Maschinenschemata lassen sich auch komplizierte Turingmaschinen simulieren und bauen. Übersichtliche Baumstruktur um mehrer Automaten in einer Datei zu speichern.

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)

Benutzungshinweise:

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.


Bachelorarbeit über den CoAn-Simulator (Deutsch), 2018
Vortrag über CoAn am 8.März 2004 um 1800 im Seminarraum E142, Uni Klu
Vortragsfolien (update 19.03)