A Python library for simulating automata and Turing machines

*Copyright 2016 Caleb Evans*

*Released under the MIT license*

Automata is a Python 3 library which implements the structures and algorithms I am learning in my Automata Theory class, particularly finite automata and Turing machines.

Automata requires Python 3.4 or newer.

## Installing

You can install the latest version of Automata via pip:

pip install automata-lib

## API

### class Automaton

The `Automaton` class is an abstract base class from which all
automata (including Turing machines) inherit. As such, it cannot be
instantiated on its own; you must use a defined subclasses instead (or
you may create your own subclass if you’re feeling adventurous). The
`Automaton` class can be found under `automata/shared/automaton.py`.

If you wish to subclass `Automaton`, you can import it like so:

from automata.shared.automaton import Automaton

### class FA

The `FA` class is an abstract base class from which all finite
automata inherit. As such, it cannot be instantiated on its own; you
must use the `DFA` and `NFA` classes instead (or you may create your
own subclass if you’re feeling adventurous). The `FA` class can be
found under `automata/fa/fa.py`.

If you wish to subclass `FA`, you can import it like so:

from automata.fa.fa import FA

### class DFA

The `DFA` class is a subclass of class `FA` which represents a
deterministic finite automaton. The `DFA` class can be found under
`automata/fa/dfa.py`.

#### DFA properties

Every DFA instance has the following properties:

`states`: a`set`of the DFA’s valid states, each of which must be represented as a string`input_symbols`: a`set`of the DFA’s valid input symbols, each of which must also be represented as a string`transitions`: a`dict`consisting of the transitions for each state. Each key is a state name and each value is a`dict`which maps a symbol (the key) to a state (the value).`initial_state`: the name of the initial state for this DFA`final_states`: a`set`of final states for this DFA

All of these properties must be supplied when the DFA is instantiated (see the examples below).

from automata.fa.dfa import DFA # DFA which matches all binary strings ending in an odd number of '1's dfa = DFA( states={'q0', 'q1', 'q2'}, input_symbols={'0', '1'}, transitions={ 'q0': {'0': 'q0', '1': 'q1'}, 'q1': {'0': 'q0', '1': 'q2'}, 'q2': {'0': 'q2', '1': 'q1'} }, initial_state='q0', final_states={'q1'} )

Please note that the below DFA code examples reference the above `dfa`
object.

#### DFA.validate_input(self, input_str, step=False)

The `validate_input()` method checks whether or not the given string
is accepted by the DFA.

If the string is accepted, the method returns the state the DFA stopped on (which presumably is a valid final state).

dfa.validate_input('01') # returns 'q1'

If the string is rejected by the DFA, the method will raise a
`RejectionError`.

dfa.validate_input('011') # raises RejectionError

If you supply the `step` keyword argument with a value of `True`,
the method will return a generator which yields each state reached as
the DFA reads characters from the input string.

list(dfa.validate_input('0111', step=True)) # returns ['q0', 'q0', 'q1', 'q2', 'q1']

Note that the first yielded state is always the DFA’s initial state
(before any input has been read) and the last yielded state is always
the DFA’s final state (after all input has been read). If the string is
rejected by the DFA, the method still raises a `RejectionError`.

#### DFA.validate_self(self)

The `validate_self()` method checks whether the DFA is actually a
valid DFA. The method returns `True` if the DFA is valid; otherwise,
it will raise the appropriate exception (*e.g.* the state transition is
missing for a particular symbol). This method is automatically called
when the DFA is initialized, so it’s only really useful if a DFA object
is modified after instantiation.

#### Copying a DFA

To create a deep copy of a DFA, simply pass an `DFA` instance into the
`DFA` constructor.

dfa_copy = DFA(dfa) # returns a deep copy of dfa

### class NFA

The `NFA` class is a subclass of class `FA` which represents a
nondeterministic finite automaton. The `NFA` class can be found under
`automata/fa/nfa.py`.

#### NFA properties

Every NFA contains the same five DFA properties: `state`,
`input_symbols`, `transitions`, `initial_state`, and
`final_states`. However, the structure of the `transitions` object
has been modified slightly to accommodate the fact that a single state
can have more than one transition for the same symbol. Therefore,
instead of mapping a symbol to *one* end state in each sub-dict, each
symbol is mapped to a *set* of end states.

from automata.fa.nfa import NFA # NFA which matches strings beginning with 'a', ending with 'a', and containing # no consecutive 'b's nfa = NFA( states={'q0', 'q1', 'q2'}, input_symbols={'a', 'b'}, transitions={ 'q0': {'a': {'q1'}}, # Use '' as the key name for empty string (lambda/epsilon) transitions 'q1': {'a': {'q1'}, '': {'q2'}}, 'q2': {'b': {'q0'}} }, initial_state='q0', final_states={'q1'} )

#### NFA.validate_input(self, input_str, step=False)

The `validate_input()` method checks whether or not the given string
is accepted by the NFA.

If the string is accepted, the method returns a `set` of states the FA
stopped on (which presumably contains at least one valid final state).

nfa.validate_input('aba') # returns {'q1', 'q2'}

If the string is rejected by the NFA, the method will raise a
`RejectionError`.

nfa.validate_input('abba') # raises RejectionError

If you supply the `step` keyword argument with a value of `True`,
the method will return a generator which yields each set of states
reached as the NFA reads characters from the input string.

list(nfa.validate_input('aba', step=True)) # returns [{'q0'}, {'q1', 'q2'}, {'q0'}, {'q1', 'q2'}]

Note that the first yielded set is always the lambda closure of the
NFA’s initial state, and the last yielded set always contains the lambda
closure of at least one of the NFA’s final states (after all input has
been read). If the string is rejected by the NFA, the method still
raises a `RejectionError`.

#### NFA.validate_self(self)

The `validate_self()` method checks whether the NFA is actually a
valid NFA. The method has the same basic behavior and prescribed use
case as the `DFA.validate_self()` method, despite being less
restrictive (since NFAs are naturally less restrictive than DFAs).

#### Converting an NFA to a DFA

To create a DFA that is equivalent to an existing NFA, simply pass the
`NFA` instance to the `DFA` constructor.

from automata.fa.dfa import DFA dfa = DFA(nfa) # returns an equivalent DFA

#### Copying an NFA

To create a deep copy of an NFA, simply pass an `NFA` instance into
the `NFA` constructor.

nfa_copy = NFA(nfa) # returns a deep copy of nfa

#### class PDA

The `PDA` class is an abstract base class from which all pushdown
automata inherit. The `PDA` class can be found under
`automata/pda/pda.py`.

### class DPDA

The `DPDA` class is a subclass of class `PDA` which represents a
deterministic finite automaton. The `DPDA` class can be found under
`automata/pda/dpda.py`.

#### DPDA properties

Every DPDA instance has the following properties:

`states`: a`set`of the DPDA’s valid states, each of which must be represented as a string`input_symbols`: a`set`of the DPDA’s valid input symbols, each of which must also be represented as a string`stack_symbols`: a`set`of the DPDA’s valid stack symbols`transitions`: a`dict`consisting of the transitions for each state; see the example below for the exact syntax`initial_state`: the name of the initial state for this DPDA`initial_stack_symbol`: the name of the initial symbol on the stack for this DPDA`final_states`: a`set`of final states for this DPDA

All of these properties must be supplied when the DPDA is instantiated (see the examples below).

from automata.pda.dpda import DPDA # DPDA which which matches zero or more 'a's, followed by the same # number of 'b's (accepting by final state) dpda = DPDA( states={'q0', 'q1', 'q2', 'q3'}, input_symbols={'a', 'b'}, stack_symbols={'0', '1'}, transitions={ 'q0': { 'a': {'0': ('q1', ('1', '0'))} # transition pushes '1' to stack }, 'q1': { 'a': {'1': ('q1', ('1', '1'))}, 'b': {'1': ('q2', '')} # transition pops from stack }, 'q2': { 'b': {'1': ('q2', '')}, '': {'0': ('q3', ('0',))} # transition does not change stack } }, initial_state='q0', initial_stack_symbol='0', final_states={'q3'} )

Please note that the below DPDA code examples reference the above
`dpda` object.

#### DPDA.validate_input(self, input_str, step=False)

The `validate_input()` method checks whether or not the given string
is accepted by the DPDA.

If the string is accepted, the method returns a tuple containing the
state the DPDA stopped on (which presumably is a valid final state), as
well as a `PDAStack` object representing the DPDA’s internal stack.

dpda.validate_input('ab') # returns PDAStack(['0'])

If the string is rejected by the DPDA, the method will raise a
`RejectionError`.

dpda.validate_input('aab') # raises RejectionError

If you supply the `step` keyword argument with a value of `True`,
the method will return a generator which yields a tuple containing the
current state and the current tape as a `PDAStack` object.

[(state, stack.copy()) for state, stack in dpda.validate_input('ab', step=True)] # returns [ # ('q0', PDAStack(['0'])), # ('q1', PDAStack(['0', '1'])), # ('q3', PDAStack(['0'])), # ]

Note that the first yielded state is always the DPDA’s initial state
(before any input has been read) and the last yielded state is always
the DPDA’s final state (after all input has been read) (or possibly a
non-final state if the stack is empty). If the string is rejected by the
DPDA, the method still raises a `RejectionError`.

#### DPDA.validate_self(self)

The `validate_self()` method checks whether the DPDA is actually a
valid DPDA. The method has the same basic behavior and prescribed use
case as the `DFA.validate_self()` and `NFA.validate_self()` methods,
while (naturally) containing validation checks specific to DPDAs.

#### Copying a DPDA

To create a deep copy of a DPDA, simply pass an `DPDA` instance into
the `DPDA` constructor.

dpda_copy = DPDA(dpda) # returns a deep copy of dpda

### class TM

The `TM` class is an abstract base class from which all Turing
machines inherit. The `TM` class can be found under
`automata/tm/tm.py`.

### class DTM

The `DTM` class is a subclass of class `TM` which represents a
deterministic Turing machine. The `DTM` class can be found under
`automata/tm/dtm.py`.

#### DTM properties

Every DTM instance has the following properties:

`states`: a`set`of the DTM’s valid states, each of which must be represented as a string`input_symbols`: a`set`of the DTM’s valid input symbols represented as strings`tape_symbols`: a`set`of the DTM’s valid tape symbols represented as strings`transitions`: a`dict`consisting of the transitions for each state; each key is a state name and each value is a`dict`which maps a symbol (the key) to a state (the value)`initial_state`: the name of the initial state for this DTM`blank_symbol`: a symbol from`tape_symbols`to be used as the blank symbol for this DTM`final_states`: a`set`of final states for this DTM

All of these properties must be supplied when the DTM is instantiated (see the examples below).

from automata.tm.dtm import DTM # DTM which matches all strings beginning with '0's, and followed by # the same number of '1's dtm = DTM( states={'q0', 'q1', 'q2', 'q3', 'q4'}, input_symbols={'0', '1'}, tape_symbols={'0', '1', 'x', 'y', '.'}, transitions={ 'q0': { '0': ('q1', 'x', 'R'), 'y': ('q3', 'y', 'R') }, 'q1': { '0': ('q1', '0', 'R'), '1': ('q2', 'y', 'L'), 'y': ('q1', 'y', 'R') }, 'q2': { '0': ('q2', '0', 'L'), 'x': ('q0', 'x', 'R'), 'y': ('q2', 'y', 'L') }, 'q3': { 'y': ('q3', 'y', 'R'), '.': ('q4', '.', 'R') } }, initial_state='q0', blank_symbol='.', final_states={'q4'} )

Please note that the below DTM code examples reference the above `dtm`
object.

#### DTM.validate_input(self, input_str, step=False)

The `validate_input()` method checks whether or not the given string
is accepted by the DTM.

If the string is accepted, the method returns a tuple containing the
state the machine stopped on (which presumably is a valid final state),
as well as a `TMTape` object representing the DTM’s internal tape.

dtm.validate_input('01') # returns ('q4', TMTape('xy.'))

If the string is rejected by the DTM, the method will raise a
`RejectionError`.

dtm.validate_input('011') # raises RejectionError

If you supply the `step` keyword argument with a value of `True`,
the method will return a generator which yields a tuple containing the
current state and the current tape as a `TMTape` object.

[(state, tape.copy()) for state, tape in dtm.validate_input('01', step=True)] # returns [ # ('q0', TMTape('01')) # ('q1', TMTape('x1')) # ('q2', TMTape('xy')) # ('q0', TMTape('xy')) # ('q3', TMTape('xy')) # ('q3', TMTape('xy.')) # ]

Please note that each tuple contains a reference to (not a copy of) the
current `TMTape` object. Therefore, if you wish to store the tape at
every step, you must copy the tape as you iterate over the machine
configurations (as shown above).

Also note that the first yielded state is always the DTM’s initial state
(before any input has been read) and the last yielded state is always
the DTM’s final state (after all input has been read). If the string is
rejected by the DTM, the method still raises a `RejectionError`.

#### DTM.validate_self(self)

The `validate_self()` method checks whether the DTM is actually a
valid DTM. The method has the same basic behavior and prescribed use
case as the `DFA.validate_self()` and `NFA.validate_self()` methods,
while (naturally) containing validation checks specific to DTMs.

#### Copying a DTM

To create a deep copy of a DTM, simply pass a `DTM` instance into the
`DTM` constructor.

dtm_copy = DTM(dtm) # returns a deep copy of dtm

### Turing machine exception classes

The `automata.tm` package also includes a module for exceptions
specific to Turing machines. You can reference these exception classes
like so:

import automata.tm.exceptions as tmexceptions

#### class TMError

A base class from which all other Turing machine exceptions inherit.

#### class InvalidDirectionError

Raised if a direction specified in this machine’s transition map is not a valid direction.

## Release History

## Download Files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

File Name & Checksum SHA256 Checksum Help | Version | File Type | Upload Date |
---|---|---|---|

automata-lib-1.0.0.post4.tar.gz (11.6 kB) Copy SHA256 Checksum SHA256 | – | Source | May 2, 2017 |