Metadata-Version: 1.0
Name: automata-lib
Version: 3.0.0
Summary: A Python library for simulating automata and Turing machines
Home-page: https://github.com/caleb531/automata
Author: Caleb Evans
Author-email: caleb@calebevans.me
License: MIT
Description: Automata
        ========
        
        | *Copyright 2018 Caleb Evans*
        | *Released under the MIT license*
        
        |Build Status| |Coverage Status|
        
        Automata is a Python 3 library which implements the structures and
        algorithms for finite automata, pushdown automata, and Turing machines.
        
        Automata requires Python 3.4 or newer.
        
        Migration to v2
        ---------------
        
        If you are using Automata v1, please note that there are some
        significant changes in v2 to refine the API. If you wish to upgrade,
        please follow the `migration
        guide <https://github.com/caleb531/automata/blob/v2/MIGRATION.md>`__.
        
        Installing
        ----------
        
        You can install the latest version of Automata via pip:
        
        ::
        
           pip install automata-lib
        
        API
        ---
        
        -  `class Automaton <#class-automatonmetaclassabcmeta>`__
        
           -  `class FA <#class-faautomatonmetaclassabcmeta>`__
        
              -  `class DFA <#class-dfafa>`__
              -  `class NFA <#class-nfafa>`__
        
           -  `class PDA <#class-pdaautomatonmetaclassabcmeta>`__
        
              -  `class DPDA <#class-dpdapda>`__
              -  `class NPDA <#class-npdapda>`__
        
           -  `class TM <#class-tmautomatonmetaclassabcmeta>`__
        
              -  `class DTM <#class-dtmtm>`__
              -  `class NTM <#class-ntmtm>`__
        
        -  `Exception classes <#base-exception-classes>`__
        
           -  `Turing machine exceptions <#turing-machine-exception-classes>`__
        
        class Automaton(metaclass=ABCMeta)
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        
        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/base/automaton.py``.
        
        If you wish to subclass ``Automaton``, you can import it like so:
        
        .. code:: python
        
           from automata.base.automaton import Automaton
        
        The following methods are common to all Automaton subtypes:
        
        Automaton.read_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Reads an input string into the automaton, returning the automaton’s
        final configuration (according to its subtype). If the input is
        rejected, the method raises a ``RejectionException``.
        
        Automaton.read_input_stepwise(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Reads an input string like ``read_input()``, except instead of returning
        the final configuration, the method returns a generator. The values
        yielded by this generator depend on the automaton’s subtype.
        
        If the string is rejected by the automaton, the method still raises a
        ``RejectionException``.
        
        Automaton.accepts_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Reads an input string like ``read_input()``, except it returns a boolean
        instead of returning the automaton’s final configuration (or raising an
        exception). That is, the method always returns ``True`` if the input is
        accepted, and it always returns ``False`` if the input is rejected.
        
        Automaton.validate(self)
        ^^^^^^^^^^^^^^^^^^^^^^^^
        
        Checks whether the automaton is actually a valid automaton (according to
        its subtype). It returns ``True`` if the automaton 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 automaton is initialized,
        so it’s only really useful if a automaton object is modified after
        instantiation.
        
        Automaton.copy(self)
        ^^^^^^^^^^^^^^^^^^^^
        
        Returns a deep copy of the automaton according to its subtype.
        
        class FA(Automaton, metaclass=ABCMeta)
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        
        The ``FA`` class is an abstract base class from which all finite
        automata inherit. The ``FA`` class can be found under
        ``automata/fa/fa.py``.
        
        If you wish to subclass ``FA``, you can import it like so:
        
        .. code:: python
        
           from automata.fa.fa import FA
        
        class DFA(FA)
        ~~~~~~~~~~~~~
        
        The ``DFA`` class is a subclass of ``FA`` and represents a deterministic
        finite automaton. It can be found under ``automata/fa/dfa.py``.
        
        Every DFA has the following (required) properties:
        
        1. ``states``: a ``set`` of the DFA’s valid states, each of which must
           be represented as a string
        
        2. ``input_symbols``: a ``set`` of the DFA’s valid input symbols, each
           of which must also be represented as a string
        
        3. ``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).
        
        4. ``initial_state``: the name of the initial state for this DFA
        
        5. ``final_states``: a ``set`` of final states for this DFA
        
        .. code:: python
        
           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'}
           )
        
        DFA.read_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Returns the final state the DFA stopped on, if the input is accepted.
        
        .. code:: python
        
           dfa.read_input('01')  # returns 'q1'
        
        .. code:: python
        
           dfa.read_input('011')  # raises RejectionException
        
        DFA.read_input_stepwise(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Yields each state reached as the DFA reads characters from the input
        string, if the input is accepted.
        
        .. code:: python
        
           dfa.read_input_stepwise('0111')
           # yields:
           # 'q0'
           # 'q0'
           # 'q1'
           # 'q2'
           # 'q1'
        
        DFA.accepts_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        .. code:: python
        
           if dfa.accepts_input(my_input_str):
               print('accepted')
           else:
               print('rejected')
        
        DFA.validate(self)
        ^^^^^^^^^^^^^^^^^^
        
        .. code:: python
        
           dfa.validate()  # returns True
        
        DFA.copy(self)
        ^^^^^^^^^^^^^^
        
        .. code:: python
        
           dfa.copy()  # returns deep copy of dfa
        
        DFA.minify(self)
        ^^^^^^^^^^^^^^^^
        
        Creates a minimal DFA which accepts the same inputs as the old one.
        Unreachable states are removed and equivalent states are merged.
        
        .. code:: python
        
           minimal_dfa = dfa.minify()
        
        DFA.from_nfa(cls, nfa)
        ^^^^^^^^^^^^^^^^^^^^^^
        
        Creates a DFA that is equivalent to the given NFA.
        
        .. code:: python
        
           from automata.fa.dfa import DFA
           from automata.fa.nfa import NFA
           dfa = DFA.from_nfa(nfa)  # returns an equivalent DFA
        
        class NFA(FA)
        ~~~~~~~~~~~~~
        
        The ``NFA`` class is a subclass of ``FA`` and represents a
        nondeterministic finite automaton. It can be found under
        ``automata/fa/nfa.py``.
        
        Every NFA has 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.
        
        .. code:: python
        
           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.read_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Returns a set of final states the FA stopped on, if the input is
        accepted.
        
        .. code:: python
        
           nfa.read_input('aba')  # returns {'q1', 'q2'}
        
        .. code:: python
        
           nfa.read_input('abba')  # raises RejectionException
        
        NFA.read_input_stepwise(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Yields each set of states reached as the NFA reads characters from the
        input string, if the input is accepted.
        
        .. code:: python
        
           nfa.read_input_stepwise('aba')
           # yields:
           # {'q0'}
           # {'q1', 'q2'}
           # {'q0'}
           # {'q1', 'q2'}
        
        NFA.accepts_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        .. code:: python
        
           if nfa.accepts_input(my_input_str):
               print('accepted')
           else:
               print('rejected')
        
        NFA.validate(self)
        ^^^^^^^^^^^^^^^^^^
        
        .. code:: python
        
           nfa.validate()  # returns True
        
        NFA.copy(self)
        ^^^^^^^^^^^^^^
        
        .. code:: python
        
           nfa.copy()  # returns deep copy of nfa
        
        NFA.from_dfa(cls, dfa)
        ^^^^^^^^^^^^^^^^^^^^^^
        
        Creates an NFA that is equivalent to the given DFA.
        
        .. code:: python
        
           from automata.fa.nfa import NFA
           from automata.fa.dfa import DFA
           nfa = NFA.from_dfa(dfa)  # returns an equivalent NFA
        
        class PDA(Automaton, metaclass=ABCMeta)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        The ``PDA`` class is an abstract base class from which all pushdown
        automata inherit. It can be found under ``automata/pda/pda.py``.
        
        class DPDA(PDA)
        ~~~~~~~~~~~~~~~
        
        The ``DPDA`` class is a subclass of ``PDA`` and represents a
        deterministic finite automaton. It can be found under
        ``automata/pda/dpda.py``.
        
        Every DPDA has the following (required) properties:
        
        1. ``states``: a ``set`` of the DPDA’s valid states, each of which must
           be represented as a string
        
        2. ``input_symbols``: a ``set`` of the DPDA’s valid input symbols, each
           of which must also be represented as a string
        
        3. ``stack_symbols``: a ``set`` of the DPDA’s valid stack symbols
        
        4. ``transitions``: a ``dict`` consisting of the transitions for each
           state; see the example below for the exact syntax
        
        5. ``initial_state``: the name of the initial state for this DPDA
        
        6. ``initial_stack_symbol``: the name of the initial symbol on the stack
           for this DPDA
        
        7. ``final_states``: a ``set`` of final states for this DPDA
        
        .. code:: python
        
           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'}
           )
        
        DPDA.read_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Returns a ``PDAConfiguration`` object representing the DPDA’s config.
        This is basically a tuple containing the final state the DPDA stopped
        on, the remaining input (an empty string) as well as a ``PDAStack``
        object representing the DPDA’s stack (if the input is accepted).
        
        .. code:: python
        
           dpda.read_input('ab')  # returns PDAConfiguration('q3', '', PDAStack(('0')))
        
        .. code:: python
        
           dpda.read_input('aab')  # raises RejectionException
        
        DPDA.read_input_stepwise(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Yields ``PDAConfiguration`` objects. These are basically tuples
        containing the current state, the remaining input and the current stack
        as a ``PDAStack`` object, if the input is accepted.
        
        .. code:: python
        
           dpda.read_input_stepwise('ab')
           # yields:
           # PDAConfiguration('q0', 'ab', PDAStack(('0')))
           # PDAConfiguration('q1', 'a', PDAStack(('0', '1')))
           # PDAConfiguration('q3', '', PDAStack(('0')))
        
        DPDA.accepts_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        .. code:: python
        
           if dpda.accepts_input(my_input_str):
               print('accepted')
           else:
               print('rejected')
        
        DPDA.validate(self)
        ^^^^^^^^^^^^^^^^^^^
        
        .. code:: python
        
           dpda.validate()  # returns True
        
        DPDA.copy(self)
        ^^^^^^^^^^^^^^^
        
        .. code:: python
        
           dpda.copy()  # returns deep copy of dpda
        
        class NPDA(PDA)
        ~~~~~~~~~~~~~~~
        
        The ``NPDA`` class is a subclass of ``PDA`` and represents a
        nondeterministic pushdown automaton. It can be found under
        ``automata/pda/npda.py``.
        
        Every NPDA has the following (required) properties:
        
        1. ``states``: a ``set`` of the NPDA’s valid states, each of which must
           be represented as a string
        
        2. ``input_symbols``: a ``set`` of the NPDA’s valid input symbols, each
           of which must also be represented as a string
        
        3. ``stack_symbols``: a ``set`` of the NPDA’s valid stack symbols
        
        4. ``transitions``: a ``dict`` consisting of the transitions for each
           state; see the example below for the exact syntax
        
        5. ``initial_state``: the name of the initial state for this NPDA
        
        6. ``initial_stack_symbol``: the name of the initial symbol on the stack
           for this NPDA
        
        7. ``final_states``: a ``set`` of final states for this NPDA
        
        .. code:: python
        
           from automata.pda.npda import NPDA
           # NPDA which matches palindromes consisting of 'a's and 'b's
           # (accepting by final state)
           # q0 reads the first half of the word, q1 the other half, q2 accepts.
           # But we have to guess when to switch.
           npda = NPDA(
               states={'q0', 'q1', 'q2'},
               input_symbols={'a', 'b'},
               stack_symbols={'A', 'B', '#'},
               transitions={
                   'q0': {
                       '': {
                           '#': {('q2', '#')},
                       },
                       'a': {
                           '#': {('q0', ('A', '#'))},
                           'A': {
                               ('q0', ('A', 'A')),
                               ('q1', ''),
                           },
                           'B': {('q0', ('A', 'B'))},
                       },
                       'b': {
                           '#': {('q0', ('B', '#'))},
                           'A': {('q0', ('B', 'A'))},
                           'B': {
                               ('q0', ('B', 'B')),
                               ('q1', ''),
                           },
                       },
                   },
                   'q1': {
                       '': {'#': {('q2', '#')}},
                       'a': {'A': {('q1', '')}},
                       'b': {'B': {('q1', '')}},
                   },
               },
               initial_state='q0',
               initial_stack_symbol='#',
               final_states={'q2'}
           )
        
        NPDA.read_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Returns a ``set`` of ``PDAConfiguration``\ s representing all of the
        NPDA’s configurations. Each of these is basically a tuple containing the
        final state the NPDA stopped on, the remaining input (an empty string)
        as well as a ``PDAStack`` object representing the NPDA’s stack (if the
        input is accepted).
        
        .. code:: python
        
           npda.read_input("aaaa") # returns {PDAConfiguration('q2', '', PDAStack('#',))}
        
        .. code:: python
        
           npda.read_input('ab')  # raises RejectionException
        
        NPDA.read_input_stepwise(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Yields ``set``\ s of ``PDAConfiguration`` object. Each of these is
        basically a tuple containing the current state, the remaining input and
        the current stack as a ``PDAStack`` object, if the input is accepted.
        
        .. code:: python
        
           npda.read_input_stepwise('aa')
           # yields:
           # {PDAConfiguration('q0', 'aa', PDAStack('#',))}
           # {PDAConfiguration('q0', 'a', PDAStack('#', 'A')), PDAConfiguration('q2', 'aa', PDAStack('#',))}
           # {PDAConfiguration('q0', '', PDAStack('#', 'A', 'A')), PDAConfiguration('q1', '', PDAStack('#',))}
           # {PDAConfiguration('q2', '', PDAStack('#',))}
        
        NPDA.accepts_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        .. code:: python
        
           if npda.accepts_input(my_input_str):
               print('accepted')
           else:
               print('rejected')
        
        NPDA.validate(self)
        ^^^^^^^^^^^^^^^^^^^
        
        .. code:: python
        
           npda.validate()  # returns True
        
        NPDA.copy(self)
        ^^^^^^^^^^^^^^^
        
        .. code:: python
        
           npda.copy()  # returns deep copy of npda
        
        class TM(Automaton, metaclass=ABCMeta)
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        
        The ``TM`` class is an abstract base class from which all Turing
        machines inherit. It can be found under ``automata/tm/tm.py``.
        
        class DTM(TM)
        ~~~~~~~~~~~~~
        
        The ``DTM`` class is a subclass of ``TM`` and represents a deterministic
        Turing machine. It can be found under ``automata/tm/dtm.py``.
        
        Every DTM has the following (required) properties:
        
        1. ``states``: a ``set`` of the DTM’s valid states, each of which must
           be represented as a string
        
        2. ``input_symbols``: a ``set`` of the DTM’s valid input symbols
           represented as strings
        
        3. ``tape_symbols``: a ``set`` of the DTM’s valid tape symbols
           represented as strings
        
        4. ``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)
        
        5. ``initial_state``: the name of the initial state for this DTM
        
        6. ``blank_symbol``: a symbol from ``tape_symbols`` to be used as the
           blank symbol for this DTM
        
        7. ``final_states``: a ``set`` of final states for this DTM
        
        .. code:: python
        
           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'}
           )
        
        The direction ``N`` (for no movement) is also supported.
        
        DTM.read_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Returns a ``TMConfiguration``. This is basically a tuple containing the
        final state the machine stopped on, as well as a ``TMTape`` object
        representing the DTM’s internal tape (if the input is accepted).
        
        .. code:: python
        
           dtm.read_input('01')  # returns TMConfiguration('q4', TMTape('xy..', 3))
        
        Calling ``config.print()`` will produce a more readable output:
        
        .. code:: python
        
           dtm.read_input('01').print()
           # q4: xy..
           #        ^
        
        .. code:: python
        
           dtm.read_input('011')  # raises RejectionException
        
        DTM.read_input_stepwise(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Yields ``TMConfiguration``\ s. Those are basically tuples containing the
        current state and the current tape as a ``TMTape`` object.
        
        .. code:: python
        
           dtm.read_input_stepwise('01')
           # yields:
           # TMConfiguration('q0', TMTape('01', 0))
           # TMConfiguration('q1', TMTape('x1', 1))
           # TMConfiguration('q2', TMTape('xy', 0))
           # TMConfiguration('q0', TMTape('xy', 1))
           # TMConfiguration('q3', TMTape('xy.', 2))
           # TMConfiguration('q4', TMTape('xy..', 3))
        
        DTM.accepts_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        .. code:: python
        
           if dtm.accepts_input(my_input_str):
               print('accepted')
           else:
               print('rejected')
        
        DTM.validate(self)
        ^^^^^^^^^^^^^^^^^^
        
        .. code:: python
        
           dtm.validate()  # returns True
        
        DTM.copy(self)
        ^^^^^^^^^^^^^^
        
        .. code:: python
        
           dtm.copy()  # returns deep copy of dtm
        
        class NTM(TM)
        ~~~~~~~~~~~~~
        
        The ``NTM`` class is a subclass of ``TM`` and represents a
        nondeterministic Turing machine. It can be found under
        ``automata/tm/ntm.py``.
        
        Every NTM has the following (required) properties:
        
        1. ``states``: a ``set`` of the NTM’s valid states, each of which must
           be represented as a string
        
        2. ``input_symbols``: a ``set`` of the NTM’s valid input symbols
           represented as strings
        
        3. ``tape_symbols``: a ``set`` of the NTM’s valid tape symbols
           represented as strings
        
        4. ``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 set of states (the values)
        
        5. ``initial_state``: the name of the initial state for this NTM
        
        6. ``blank_symbol``: a symbol from ``tape_symbols`` to be used as the
           blank symbol for this NTM
        
        7. ``final_states``: a ``set`` of final states for this NTM
        
        .. code:: python
        
           from automata.tm.ntm import NTM
           # NTM which matches all strings beginning with '0's, and followed by
           # the same number of '1's
           # Note that the nondeterminism is not really used here.
           ntm = NTM(
               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'}
           )
        
        The direction ``N`` (for no movement) is also supported.
        
        NTM.read_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Returns a set of ``TMConfiguration``\ s. These are basically tuples
        containing the final state the machine stopped on, as well as a
        ``TMTape`` object representing the DTM’s internal tape (if the input is
        accepted).
        
        .. code:: python
        
           ntm.read_input('01')  # returns {TMConfiguration('q4', TMTape('xy..', 3))}
        
        Calling ``config.print()`` will produce a more readable output:
        
        .. code:: python
        
           ntm.read_input('01').pop().print()
           # q4: xy..
           #        ^
        
        .. code:: python
        
           ntm.read_input('011')  # raises RejectionException
        
        NTM.read_input_stepwise(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        Yields sets of ``TMConfiguration``\ s. Those are basically tuples
        containing the current state and the current tape as a ``TMTape``
        object.
        
        .. code:: python
        
           ntm.read_input_stepwise('01')
           # yields:
           # {TMConfiguration('q0', TMTape('01', 0))}
           # {TMConfiguration('q1', TMTape('x1', 1))}
           # {TMConfiguration('q2', TMTape('xy', 0))}
           # {TMConfiguration('q0', TMTape('xy', 1))}
           # {TMConfiguration('q3', TMTape('xy.', 2))}
           # {TMConfiguration('q4', TMTape('xy..', 3))}
        
        NTM.accepts_input(self, input_str)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        
        .. code:: python
        
           if ntm.accepts_input(my_input_str):
               print('accepted')
           else:
               print('rejected')
        
        NTM.validate(self)
        ^^^^^^^^^^^^^^^^^^
        
        .. code:: python
        
           ntm.validate()  # returns True
        
        NTM.copy(self)
        ^^^^^^^^^^^^^^
        
        .. code:: python
        
           ntm.copy()  # returns deep copy of ntm
        
        Base exception classes
        ~~~~~~~~~~~~~~~~~~~~~~
        
        The library also includes a number of exception classes to ensure that
        errors never pass silently (unless explicitly silenced). See
        ``automata/base/exceptions.py`` for these class definitions.
        
        To reference these exceptions (so as to catch them in a ``try..except``
        block or whatnot), simply import ``automata.base.exceptions`` however
        you’d like:
        
        .. code:: python
        
           import automata.base.exceptions as exceptions
        
        class AutomatonException
        ^^^^^^^^^^^^^^^^^^^^^^^^
        
        A base class from which all other automata exceptions inherit (including
        finite automata and Turing machines).
        
        class InvalidStateError
        ^^^^^^^^^^^^^^^^^^^^^^^
        
        Raised if a state is not a valid state for this automaton.
        
        class InvalidSymbolError
        ^^^^^^^^^^^^^^^^^^^^^^^^
        
        Raised if a symbol is not a valid symbol for this automaton.
        
        class MissingStateError
        ^^^^^^^^^^^^^^^^^^^^^^^
        
        Raised if a state is missing from the automaton definition.
        
        class MissingSymbolError
        ^^^^^^^^^^^^^^^^^^^^^^^^
        
        Raised if a symbol is missing from the automaton definition.
        
        class InitialStateError
        ^^^^^^^^^^^^^^^^^^^^^^^
        
        Raised if the initial state fails to meet some required condition for
        this type of automaton.
        
        class FinalStateError
        ^^^^^^^^^^^^^^^^^^^^^
        
        Raised if a final state fails to meet some required condition for this
        type of automaton.
        
        class RejectionException
        ^^^^^^^^^^^^^^^^^^^^^^^^
        
        Raised if the automaton stopped on a non-final state after validating
        input.
        
        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:
        
        .. code:: python
        
           import automata.tm.exceptions as tm_exceptions
        
        class TMException
        ^^^^^^^^^^^^^^^^^
        
        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.
        
        .. |Build Status| image:: https://travis-ci.org/caleb531/automata.svg?branch=master
           :target: https://travis-ci.org/caleb531/automata
        .. |Coverage Status| image:: https://coveralls.io/repos/caleb531/automata/badge.svg?branch=master
           :target: https://coveralls.io/r/caleb531/automata?branch=master
        
Keywords: automata turing machine
Platform: UNKNOWN
