Turing and Auto­maton Simu­lator

CoAn - Compiler and Automaton Network Simulator

qcoan version 2.0
(turing simulator & automaton simulator)
sourcecodes as tar.bz2, and as .zip (now with GPLv3) windows executable, ucrtbased.dll Linux binaries
CoAn LE Version 1.1
(turing simulator & automaton simulator)
executable (2004, German)  
CoAn TLE Version 1.0
(turing simulator)
executable (German) docu. and examples in German
(Michael Leitner)
SHA512SUMS: software/SHA512SUMS.signed

Please sign our Contributor License Agreement if you want to contribute code. Otherwise we can not assimilate and re-distribute your changes here at elstel.org

**new** in version 2.0: fully implemented in C++/Qt for Linux and Windows, non-deterministic Turing machines, multi character edges and edges with character sets for finite automata, parameterized machine schemata with power/superscript expression to repeat an automaton a certain number of times.

Hint: Open Test2.atm to get a few examples. If the windows executables should not run then copy ucrtbased.dll into the coan-2.0-exe directory.

Full-fledged automaton simulator which can run finite automata, pushdown automata, Turing machines and machine schemata for deterministic and non-deterministic automata (all simultaneously active states are shown in light yellow). Non-deterministic pushdown automata are shown with all possible stack contents for a certain activation. Use machine schemata to create and simulate more complicated Turing machines. Clear tree structure to view, execute and safe different automata within a single file.

Motivation: It is a program that can simulate non-deterministic Turing machines and pushdown automata. These machines are defined by theoretical information science. You use finite automata for regular expressions and pushdown automata f.i. for parsing programming languages. Turing machines are used as a model of computability and to implement unrestricted grammars or grammars with context i.e. Ax → xA. The program will currently be useful for modelling, design and for educational purposes. Nonetheless it is planned to implement a console version of qcoan called coan so that you may use it f.i. instead of a regexp matcher or as a mini parser. The implementation is organized in three layers so that the program can also be compiled without a GUI.

The following abbreviations are used: PDA - pusdown automaton, DFA - deterministic finite automaton, NFA - non-deterministic finite automaton, NPDA non-deterministic pushdown automaton, NDTM non-deterministic Turing machine

usage hints:

The empty set is displayed with the symbol “∅” but can be entered simply as a string with no characters. f.i. the string “α≠∅//α” can be entered as “\alpha!=//\alpha”. The full set of all characters can be entered as the complement of the empty set: “!=” If there is no variable to be assigned at the left the non-equal operator just complements the character set at the right. An empty string as a whole is interpreted as epsilon transition.

There are multi step transitions with some characters read in sequence like “a\+b\+c” which is translated into “a⚬b⚬c”. If the rings are left out qcoan will also assume a multi step transition. If you want a transition with a character set reading only a single character (one of a,b,c) then enter “abc\+” or “abc⚬”. As soon as you use the set minus operator “\-” - “∖” or the character set range operator “a\..c” - “a…c” qcoan will also assume a transition with a character set rather than a multi step transition.

Finally if you have multiple variable transitions within the state of an automaton do not forget to use the setminus operator in order to avoid ambiguities: “α”, “β∖α”, “γ∖αβ”. Variables in push down automata are transition local while variables in turing machines and machine schemata use to be global. Additionally all types of automata can have predefined variables defined before the automaton starts to run.

bachelor thesis about the CoAn simulator (German), 2018