Computational structures

A computational structure in Grafstate defines a logical process that takes an input string and decides (YES or NO) whether the string is accepted by the process. A computational structure can be simulated by the Grafstate Simulator. Each simulation shows all computational steps performed by the process when reading an input string.

Automata (state machines)

Name
Grafstate structure type
Brief description
dfa
This finite state machine is a deterministic process with no memory. It recognizes a regular language. The simulation of a DFA produces a computation sequence.
nfa
This finite state machine is a non-deterministic process with no memory. It recognizes a regular language. The simulation of an NFA produces a nondeterminism tree.
gnfa
This finite state machine is a non-deterministic process with no memory. GNFAs are constructed to aid in the process of converting from a DFA to an equivalent regular expression. GNFAs are not used in actual computation. Therefore, Grafstate does not simulate GNFAs.
pda
This state machine is a non-deterministic process that is a stack as its memory. It recognizes a context-free language. The simulation of a PDA produces a stack trace.
tm
This state machine uses a tape as its memory. The simulation of a Turing machine produces a computational history.