Automata

Automata is a C# library that uses language-generating machines to process sequences of symbols or generate yes/no answers. Each available machine follows its theoretical implementation as closely as possible; to make the process simple and intuitive, each constructor is made to match the mathematical definition of the automaton. Simply put, this library is capable of approximately anything that a theoretical machine is capable of.

To obtain the latest version of this library, visit the releases page.
View the full API documentation at this repository's Github Pages

Usage

Everything in the library is located in the System.Automata namespace. To create a machine, simply use its constructor. One a machine is constructed, strings may be evaluated by calling Run() on a string or IEnumerable<char>. If the call returns true, the string is accepted by the machine (and thus, is a member of the language generated by the machine.) As the instance of a machine will only store the information making up the machine's definition, the machines defined here should be thread safe, but this has not been thorougly tested as of yet. Each machine will contain a collection States of States, an initial State, at least one Alphabet, and a transition function implemented as a collection of transitions. This library contains the following machines:

Finite Automaton

An FA is a state machine that has no memory. A string is evaluated by moving between states based on each character. A FiniteAutomaton is defined to be deterministic; this means that for each state, there is no more than one possible move for a given symbol; breaking this rule will throw an ArgumentException.

FiniteAutomaton(States q, Alphabet a, TransitionFunction d, State q0, AcceptingStates f)

Non-deterministic Finite Automaton

An NFA is a generalization of an FA which allows for multiple possible moves from a state given the same symbol, as well as null transitions (transitions that do not consume a symbol.) To perform a null transition, set the transition symbol to be Alphabet.EmptyString (representing ε, the empty string). The machine will be able to perform a null transition from any state, even if it has run out of symbols in the input.

NondeterministicFiniteAutomaton(States q, Alphabet a, NondeterministicTransitionFunction d, State q0, AcceptingStates f)

Pushdown Automaton

A PDA is a non-deterministic state machine that contains a single unit of stack memory. When the machine is started, the stack will always be initialized with the initial stack symbol, Alphabet.Z. At any given time, the machine does not know how large the stack is, or what the stack contains aside from the top stack symbol. To modify the stack, replace the stack symbol with a string. For example, to add a to a quasi-empty stack, replace Z with aZ. To remove a, replace a with the empty string (Alphabet.EmptyString). If the stack has been emptied (including Z), the machine will halt in failure. To accept, the machine need only consume the input and land in an accepting state.

PushdownAutomaton(States q, Alphabet a, StackAlphabet g, PushdownTransitionFunction d, State q0, AcceptingStates f)

Turing Machine

A TM is a non-deterministic state machine similar to the Von Neumann architecture; instead of consuming an input sequence of symbols, it contains memory divided into a theoretically infinite number of memory cells each containing at most one symbol. If a tape cell does not contain a symbol, it contains the blank symbol, Alphabet.Blank. When the machine is run, the machine will automatically fill the tape with a single blank symbol followed by the entire input sequence (and a potentially infinite number of blanks after that.) The machine may then read the tape one cell at a time, and after each read, it must replace the symbol (including with itself or a blank), and then it may chose to move left one cell, right one cell, or to not move at all. To stop execution, the machine can move to one of two pre-defined states, State.Ha (halt-accept) or State.Hr (halt-reject); Run() will return true if the machine reaches Ha or false if it reaches Hr, no matter the tape contents. Additionally, the machine will move to Hr if the machine tries to move left of tape cell 0. When running the machine, Run has an optional parameter, out char[] o, that will return the contents of the tape for the purpose of performing calculations (in most cases, the machine must reach Ha for this to be useful.)

TuringMachine(States q, Alphabet a, TapeAlphabet g, TuringTransitionFunction tf, State q0)

Multitape Turing Machine

A MTM is a special kind of turing machine that utilizes k>0 tapes. When initializing the machine, the input will be written to tape 0 in a similar method as a TuringMachine, and the remaining k-1 tapes will contain all blanks. A transition for a multitape turing machine will contain an array of values that each tape head should currently be pointing to, and an array of 2-tuples containing the character to replace each tape cell with, and the direction to move in; in both cases, the array index referes to each tape; in other words, each array goes from 0 to k-1 and 0 is the first tape, 1 is the second tape, and so on.

MultitapeTuringMachine(States q, Alphabet a, TapeAlphabet g, MultitapeTuringTransitionFunction tf, State q0, int k = 1)

Example

Let L be the language of binary numbers that are divisible by 3 (i.e. nmod3 = 0). Let M = (Q, S, d, q0, F) be a finite automaton such that L(M) = L, where
Q = {q0, q1, q2},
S = {0, 1},
F = {q0},
d = QxS -> Q = {
(q0, 0) = q0,
(q0, 1) = q1,
(q1, 0) = q2,
(q1, 1) = q0,
(q2, 0) = q1,
(q2, 0) = q2
}

We may directly translate the above definition into the following code:

var q = new States(3);
var f = new AcceptingStates(q[0]);
var tf = new TransitionFunction() {
  new Transition(q[0], '0', q[0]),
  new Transition(q[0], '1', q[1]),
  new Transition(q[1], '1', q[0]),
  new Transition(q[1], '0', q[2]),
  new Transition(q[2], '0', q[1]),
  new Transition(q[2], '1', q[2])
};
var m = new FiniteAutomaton(q, Alphabet.Binary, tf, q[0], f);

To test, we execute:

Console.WriteLine(m.Run("1011101110000"));

which will print: True

Licensing

This library is provided for free under the GNU-GPL3 license. It is provided without any implied warranty in the hope that it will prove useful to somebody in their studies or their own software. Should a bug be found, please feel free to file a bug report at https://github.com/hanabanashiku/Automata.