{ "info": { "author": "Caleb Evans", "author_email": "caleb@calebevans.me", "bugtrack_url": null, "classifiers": [], "description": "Automata\n========\n\n| *Copyright 2016-2019 Caleb Evans*\n| *Released under the MIT license*\n\n|Build Status| |Coverage Status|\n\nAutomata is a Python 3 library which implements the structures and\nalgorithms for finite automata, pushdown automata, and Turing machines.\n\nAutomata requires Python 3.4 or newer.\n\nMigration to v2 or v3\n---------------------\n\nIf you are using Automata v1 and wish to migrate to v2 or v3, please\nfollow the `migration\nguide `__.\n\nInstalling\n----------\n\nYou can install the latest version of Automata via pip:\n\n::\n\n pip install automata-lib\n\nAPI\n---\n\n- `class Automaton <#class-automatonmetaclassabcmeta>`__\n\n - `class FA <#class-faautomatonmetaclassabcmeta>`__\n\n - `class DFA <#class-dfafa>`__\n - `class NFA <#class-nfafa>`__\n\n - `class PDA <#class-pdaautomatonmetaclassabcmeta>`__\n\n - `class DPDA <#class-dpdapda>`__\n - `class NPDA <#class-npdapda>`__\n\n - `class TM <#class-tmautomatonmetaclassabcmeta>`__\n\n - `class DTM <#class-dtmtm>`__\n - `class NTM <#class-ntmtm>`__\n\n- `Exception classes <#base-exception-classes>`__\n\n - `Turing machine exceptions <#turing-machine-exception-classes>`__\n\nclass Automaton(metaclass=ABCMeta)\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\nThe ``Automaton`` class is an abstract base class from which all\nautomata (including Turing machines) inherit. As such, it cannot be\ninstantiated on its own; you must use a defined subclasses instead (or\nyou may create your own subclass if you\u2019re feeling adventurous). The\n``Automaton`` class can be found under ``automata/base/automaton.py``.\n\nIf you wish to subclass ``Automaton``, you can import it like so:\n\n.. code:: python\n\n from automata.base.automaton import Automaton\n\nThe following methods are common to all Automaton subtypes:\n\nAutomaton.read_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nReads an input string into the automaton, returning the automaton\u2019s\nfinal configuration (according to its subtype). If the input is\nrejected, the method raises a ``RejectionException``.\n\nAutomaton.read_input_stepwise(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nReads an input string like ``read_input()``, except instead of returning\nthe final configuration, the method returns a generator. The values\nyielded by this generator depend on the automaton\u2019s subtype.\n\nIf the string is rejected by the automaton, the method still raises a\n``RejectionException``.\n\nAutomaton.accepts_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nReads an input string like ``read_input()``, except it returns a boolean\ninstead of returning the automaton\u2019s final configuration (or raising an\nexception). That is, the method always returns ``True`` if the input is\naccepted, and it always returns ``False`` if the input is rejected.\n\nAutomaton.validate(self)\n^^^^^^^^^^^^^^^^^^^^^^^^\n\nChecks whether the automaton is actually a valid automaton (according to\nits subtype). It returns ``True`` if the automaton is valid; otherwise,\nit will raise the appropriate exception (*e.g.* the state transition is\nmissing for a particular symbol).\n\nThis method is automatically called when the automaton is initialized,\nso it\u2019s only really useful if a automaton object is modified after\ninstantiation.\n\nAutomaton.copy(self)\n^^^^^^^^^^^^^^^^^^^^\n\nReturns a deep copy of the automaton according to its subtype.\n\nclass FA(Automaton, metaclass=ABCMeta)\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\nThe ``FA`` class is an abstract base class from which all finite\nautomata inherit. The ``FA`` class can be found under\n``automata/fa/fa.py``.\n\nIf you wish to subclass ``FA``, you can import it like so:\n\n.. code:: python\n\n from automata.fa.fa import FA\n\nclass DFA(FA)\n~~~~~~~~~~~~~\n\nThe ``DFA`` class is a subclass of ``FA`` and represents a deterministic\nfinite automaton. It can be found under ``automata/fa/dfa.py``.\n\nEvery DFA has the following (required) properties:\n\n1. ``states``: a ``set`` of the DFA\u2019s valid states, each of which must\n be represented as a string\n\n2. ``input_symbols``: a ``set`` of the DFA\u2019s valid input symbols, each\n of which must also be represented as a string\n\n3. ``transitions``: a ``dict`` consisting of the transitions for each\n state. Each key is a state name and each value is a ``dict`` which\n maps a symbol (the key) to a state (the value).\n\n4. ``initial_state``: the name of the initial state for this DFA\n\n5. ``final_states``: a ``set`` of final states for this DFA\n\n.. code:: python\n\n from automata.fa.dfa import DFA\n # DFA which matches all binary strings ending in an odd number of '1's\n dfa = DFA(\n states={'q0', 'q1', 'q2'},\n input_symbols={'0', '1'},\n transitions={\n 'q0': {'0': 'q0', '1': 'q1'},\n 'q1': {'0': 'q0', '1': 'q2'},\n 'q2': {'0': 'q2', '1': 'q1'}\n },\n initial_state='q0',\n final_states={'q1'}\n )\n\nDFA.read_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nReturns the final state the DFA stopped on, if the input is accepted.\n\n.. code:: python\n\n dfa.read_input('01') # returns 'q1'\n\n.. code:: python\n\n dfa.read_input('011') # raises RejectionException\n\nDFA.read_input_stepwise(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nYields each state reached as the DFA reads characters from the input\nstring, if the input is accepted.\n\n.. code:: python\n\n dfa.read_input_stepwise('0111')\n # yields:\n # 'q0'\n # 'q0'\n # 'q1'\n # 'q2'\n # 'q1'\n\nDFA.accepts_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\n.. code:: python\n\n if dfa.accepts_input(my_input_str):\n print('accepted')\n else:\n print('rejected')\n\nDFA.validate(self)\n^^^^^^^^^^^^^^^^^^\n\n.. code:: python\n\n dfa.validate() # returns True\n\nDFA.copy(self)\n^^^^^^^^^^^^^^\n\n.. code:: python\n\n dfa.copy() # returns deep copy of dfa\n\nDFA.minify(self)\n^^^^^^^^^^^^^^^^\n\nCreates a minimal DFA which accepts the same inputs as the old one.\nUnreachable states are removed and equivalent states are merged.\n\n.. code:: python\n\n minimal_dfa = dfa.minify()\n\nDFA.from_nfa(cls, nfa)\n^^^^^^^^^^^^^^^^^^^^^^\n\nCreates a DFA that is equivalent to the given NFA.\n\n.. code:: python\n\n from automata.fa.dfa import DFA\n from automata.fa.nfa import NFA\n dfa = DFA.from_nfa(nfa) # returns an equivalent DFA\n\nclass NFA(FA)\n~~~~~~~~~~~~~\n\nThe ``NFA`` class is a subclass of ``FA`` and represents a\nnondeterministic finite automaton. It can be found under\n``automata/fa/nfa.py``.\n\nEvery NFA has the same five DFA properties: ``state``,\n``input_symbols``, ``transitions``, ``initial_state``, and\n``final_states``. However, the structure of the ``transitions`` object\nhas been modified slightly to accommodate the fact that a single state\ncan have more than one transition for the same symbol. Therefore,\ninstead of mapping a symbol to *one* end state in each sub-dict, each\nsymbol is mapped to a *set* of end states.\n\n.. code:: python\n\n from automata.fa.nfa import NFA\n # NFA which matches strings beginning with 'a', ending with 'a', and containing\n # no consecutive 'b's\n nfa = NFA(\n states={'q0', 'q1', 'q2'},\n input_symbols={'a', 'b'},\n transitions={\n 'q0': {'a': {'q1'}},\n # Use '' as the key name for empty string (lambda/epsilon) transitions\n 'q1': {'a': {'q1'}, '': {'q2'}},\n 'q2': {'b': {'q0'}}\n },\n initial_state='q0',\n final_states={'q1'}\n )\n\nNFA.read_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nReturns a set of final states the FA stopped on, if the input is\naccepted.\n\n.. code:: python\n\n nfa.read_input('aba') # returns {'q1', 'q2'}\n\n.. code:: python\n\n nfa.read_input('abba') # raises RejectionException\n\nNFA.read_input_stepwise(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nYields each set of states reached as the NFA reads characters from the\ninput string, if the input is accepted.\n\n.. code:: python\n\n nfa.read_input_stepwise('aba')\n # yields:\n # {'q0'}\n # {'q1', 'q2'}\n # {'q0'}\n # {'q1', 'q2'}\n\nNFA.accepts_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\n.. code:: python\n\n if nfa.accepts_input(my_input_str):\n print('accepted')\n else:\n print('rejected')\n\nNFA.validate(self)\n^^^^^^^^^^^^^^^^^^\n\n.. code:: python\n\n nfa.validate() # returns True\n\nNFA.copy(self)\n^^^^^^^^^^^^^^\n\n.. code:: python\n\n nfa.copy() # returns deep copy of nfa\n\nNFA.from_dfa(cls, dfa)\n^^^^^^^^^^^^^^^^^^^^^^\n\nCreates an NFA that is equivalent to the given DFA.\n\n.. code:: python\n\n from automata.fa.nfa import NFA\n from automata.fa.dfa import DFA\n nfa = NFA.from_dfa(dfa) # returns an equivalent NFA\n\nclass PDA(Automaton, metaclass=ABCMeta)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nThe ``PDA`` class is an abstract base class from which all pushdown\nautomata inherit. It can be found under ``automata/pda/pda.py``.\n\nclass DPDA(PDA)\n~~~~~~~~~~~~~~~\n\nThe ``DPDA`` class is a subclass of ``PDA`` and represents a\ndeterministic finite automaton. It can be found under\n``automata/pda/dpda.py``.\n\nEvery DPDA has the following (required) properties:\n\n1. ``states``: a ``set`` of the DPDA\u2019s valid states, each of which must\n be represented as a string\n\n2. ``input_symbols``: a ``set`` of the DPDA\u2019s valid input symbols, each\n of which must also be represented as a string\n\n3. ``stack_symbols``: a ``set`` of the DPDA\u2019s valid stack symbols\n\n4. ``transitions``: a ``dict`` consisting of the transitions for each\n state; see the example below for the exact syntax\n\n5. ``initial_state``: the name of the initial state for this DPDA\n\n6. ``initial_stack_symbol``: the name of the initial symbol on the stack\n for this DPDA\n\n7. ``final_states``: a ``set`` of final states for this DPDA\n\n8. ``acceptance_mode``: a string defining whether this DPDA accepts by\n ``'final_state'``, ``'empty_stack'``, or ``'both'``; the default is\n ``'both'``\n\n.. code:: python\n\n from automata.pda.dpda import DPDA\n # DPDA which which matches zero or more 'a's, followed by the same\n # number of 'b's (accepting by final state)\n dpda = DPDA(\n states={'q0', 'q1', 'q2', 'q3'},\n input_symbols={'a', 'b'},\n stack_symbols={'0', '1'},\n transitions={\n 'q0': {\n 'a': {'0': ('q1', ('1', '0'))} # transition pushes '1' to stack\n },\n 'q1': {\n 'a': {'1': ('q1', ('1', '1'))},\n 'b': {'1': ('q2', '')} # transition pops from stack\n },\n 'q2': {\n 'b': {'1': ('q2', '')},\n '': {'0': ('q3', ('0',))} # transition does not change stack\n }\n },\n initial_state='q0',\n initial_stack_symbol='0',\n final_states={'q3'},\n acceptance_mode='final_state'\n )\n\nDPDA.read_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nReturns a ``PDAConfiguration`` object representing the DPDA\u2019s config.\nThis is basically a tuple containing the final state the DPDA stopped\non, the remaining input (an empty string) as well as a ``PDAStack``\nobject representing the DPDA\u2019s stack (if the input is accepted).\n\n.. code:: python\n\n dpda.read_input('ab') # returns PDAConfiguration('q3', '', PDAStack(('0')))\n\n.. code:: python\n\n dpda.read_input('aab') # raises RejectionException\n\nDPDA.read_input_stepwise(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nYields ``PDAConfiguration`` objects. These are basically tuples\ncontaining the current state, the remaining input and the current stack\nas a ``PDAStack`` object, if the input is accepted.\n\n.. code:: python\n\n dpda.read_input_stepwise('ab')\n # yields:\n # PDAConfiguration('q0', 'ab', PDAStack(('0')))\n # PDAConfiguration('q1', 'a', PDAStack(('0', '1')))\n # PDAConfiguration('q3', '', PDAStack(('0')))\n\nDPDA.accepts_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\n.. code:: python\n\n if dpda.accepts_input(my_input_str):\n print('accepted')\n else:\n print('rejected')\n\nDPDA.validate(self)\n^^^^^^^^^^^^^^^^^^^\n\n.. code:: python\n\n dpda.validate() # returns True\n\nDPDA.copy(self)\n^^^^^^^^^^^^^^^\n\n.. code:: python\n\n dpda.copy() # returns deep copy of dpda\n\nclass NPDA(PDA)\n~~~~~~~~~~~~~~~\n\nThe ``NPDA`` class is a subclass of ``PDA`` and represents a\nnondeterministic pushdown automaton. It can be found under\n``automata/pda/npda.py``.\n\nEvery NPDA has the following (required) properties:\n\n1. ``states``: a ``set`` of the NPDA\u2019s valid states, each of which must\n be represented as a string\n\n2. ``input_symbols``: a ``set`` of the NPDA\u2019s valid input symbols, each\n of which must also be represented as a string\n\n3. ``stack_symbols``: a ``set`` of the NPDA\u2019s valid stack symbols\n\n4. ``transitions``: a ``dict`` consisting of the transitions for each\n state; see the example below for the exact syntax\n\n5. ``initial_state``: the name of the initial state for this NPDA\n\n6. ``initial_stack_symbol``: the name of the initial symbol on the stack\n for this NPDA\n\n7. ``final_states``: a ``set`` of final states for this NPDA\n\n8. ``acceptance_mode``: a string defining whether this NPDA accepts by\n ``'final_state'``, ``'empty_stack'``, or ``'both'``; the default is\n ``'both'``\n\n.. code:: python\n\n from automata.pda.npda import NPDA\n # NPDA which matches palindromes consisting of 'a's and 'b's\n # (accepting by final state)\n # q0 reads the first half of the word, q1 the other half, q2 accepts.\n # But we have to guess when to switch.\n npda = NPDA(\n states={'q0', 'q1', 'q2'},\n input_symbols={'a', 'b'},\n stack_symbols={'A', 'B', '#'},\n transitions={\n 'q0': {\n '': {\n '#': {('q2', '#')},\n },\n 'a': {\n '#': {('q0', ('A', '#'))},\n 'A': {\n ('q0', ('A', 'A')),\n ('q1', ''),\n },\n 'B': {('q0', ('A', 'B'))},\n },\n 'b': {\n '#': {('q0', ('B', '#'))},\n 'A': {('q0', ('B', 'A'))},\n 'B': {\n ('q0', ('B', 'B')),\n ('q1', ''),\n },\n },\n },\n 'q1': {\n '': {'#': {('q2', '#')}},\n 'a': {'A': {('q1', '')}},\n 'b': {'B': {('q1', '')}},\n },\n },\n initial_state='q0',\n initial_stack_symbol='#',\n final_states={'q2'},\n acceptance_mode='final_state'\n )\n\nNPDA.read_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nReturns a ``set`` of ``PDAConfiguration``\\ s representing all of the\nNPDA\u2019s configurations. Each of these is basically a tuple containing the\nfinal state the NPDA stopped on, the remaining input (an empty string)\nas well as a ``PDAStack`` object representing the NPDA\u2019s stack (if the\ninput is accepted).\n\n.. code:: python\n\n npda.read_input(\"aaaa\") # returns {PDAConfiguration('q2', '', PDAStack('#',))}\n\n.. code:: python\n\n npda.read_input('ab') # raises RejectionException\n\nNPDA.read_input_stepwise(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nYields ``set``\\ s of ``PDAConfiguration`` object. Each of these is\nbasically a tuple containing the current state, the remaining input and\nthe current stack as a ``PDAStack`` object, if the input is accepted.\n\n.. code:: python\n\n npda.read_input_stepwise('aa')\n # yields:\n # {PDAConfiguration('q0', 'aa', PDAStack('#',))}\n # {PDAConfiguration('q0', 'a', PDAStack('#', 'A')), PDAConfiguration('q2', 'aa', PDAStack('#',))}\n # {PDAConfiguration('q0', '', PDAStack('#', 'A', 'A')), PDAConfiguration('q1', '', PDAStack('#',))}\n # {PDAConfiguration('q2', '', PDAStack('#',))}\n\nNPDA.accepts_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\n.. code:: python\n\n if npda.accepts_input(my_input_str):\n print('accepted')\n else:\n print('rejected')\n\nNPDA.validate(self)\n^^^^^^^^^^^^^^^^^^^\n\n.. code:: python\n\n npda.validate() # returns True\n\nNPDA.copy(self)\n^^^^^^^^^^^^^^^\n\n.. code:: python\n\n npda.copy() # returns deep copy of npda\n\nclass TM(Automaton, metaclass=ABCMeta)\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\nThe ``TM`` class is an abstract base class from which all Turing\nmachines inherit. It can be found under ``automata/tm/tm.py``.\n\nclass DTM(TM)\n~~~~~~~~~~~~~\n\nThe ``DTM`` class is a subclass of ``TM`` and represents a deterministic\nTuring machine. It can be found under ``automata/tm/dtm.py``.\n\nEvery DTM has the following (required) properties:\n\n1. ``states``: a ``set`` of the DTM\u2019s valid states, each of which must\n be represented as a string\n\n2. ``input_symbols``: a ``set`` of the DTM\u2019s valid input symbols\n represented as strings\n\n3. ``tape_symbols``: a ``set`` of the DTM\u2019s valid tape symbols\n represented as strings\n\n4. ``transitions``: a ``dict`` consisting of the transitions for each\n state; each key is a state name and each value is a ``dict`` which\n maps a symbol (the key) to a state (the value)\n\n5. ``initial_state``: the name of the initial state for this DTM\n\n6. ``blank_symbol``: a symbol from ``tape_symbols`` to be used as the\n blank symbol for this DTM\n\n7. ``final_states``: a ``set`` of final states for this DTM\n\n.. code:: python\n\n from automata.tm.dtm import DTM\n # DTM which matches all strings beginning with '0's, and followed by\n # the same number of '1's\n dtm = DTM(\n states={'q0', 'q1', 'q2', 'q3', 'q4'},\n input_symbols={'0', '1'},\n tape_symbols={'0', '1', 'x', 'y', '.'},\n transitions={\n 'q0': {\n '0': ('q1', 'x', 'R'),\n 'y': ('q3', 'y', 'R')\n },\n 'q1': {\n '0': ('q1', '0', 'R'),\n '1': ('q2', 'y', 'L'),\n 'y': ('q1', 'y', 'R')\n },\n 'q2': {\n '0': ('q2', '0', 'L'),\n 'x': ('q0', 'x', 'R'),\n 'y': ('q2', 'y', 'L')\n },\n 'q3': {\n 'y': ('q3', 'y', 'R'),\n '.': ('q4', '.', 'R')\n }\n },\n initial_state='q0',\n blank_symbol='.',\n final_states={'q4'}\n )\n\nThe direction ``N`` (for no movement) is also supported.\n\nDTM.read_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nReturns a ``TMConfiguration``. This is basically a tuple containing the\nfinal state the machine stopped on, as well as a ``TMTape`` object\nrepresenting the DTM\u2019s internal tape (if the input is accepted).\n\n.. code:: python\n\n dtm.read_input('01') # returns TMConfiguration('q4', TMTape('xy..', 3))\n\nCalling ``config.print()`` will produce a more readable output:\n\n.. code:: python\n\n dtm.read_input('01').print()\n # q4: xy..\n # ^\n\n.. code:: python\n\n dtm.read_input('011') # raises RejectionException\n\nDTM.read_input_stepwise(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nYields ``TMConfiguration``\\ s. Those are basically tuples containing the\ncurrent state and the current tape as a ``TMTape`` object.\n\n.. code:: python\n\n dtm.read_input_stepwise('01')\n # yields:\n # TMConfiguration('q0', TMTape('01', 0))\n # TMConfiguration('q1', TMTape('x1', 1))\n # TMConfiguration('q2', TMTape('xy', 0))\n # TMConfiguration('q0', TMTape('xy', 1))\n # TMConfiguration('q3', TMTape('xy.', 2))\n # TMConfiguration('q4', TMTape('xy..', 3))\n\nDTM.accepts_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\n.. code:: python\n\n if dtm.accepts_input(my_input_str):\n print('accepted')\n else:\n print('rejected')\n\nDTM.validate(self)\n^^^^^^^^^^^^^^^^^^\n\n.. code:: python\n\n dtm.validate() # returns True\n\nDTM.copy(self)\n^^^^^^^^^^^^^^\n\n.. code:: python\n\n dtm.copy() # returns deep copy of dtm\n\nclass NTM(TM)\n~~~~~~~~~~~~~\n\nThe ``NTM`` class is a subclass of ``TM`` and represents a\nnondeterministic Turing machine. It can be found under\n``automata/tm/ntm.py``.\n\nEvery NTM has the following (required) properties:\n\n1. ``states``: a ``set`` of the NTM\u2019s valid states, each of which must\n be represented as a string\n\n2. ``input_symbols``: a ``set`` of the NTM\u2019s valid input symbols\n represented as strings\n\n3. ``tape_symbols``: a ``set`` of the NTM\u2019s valid tape symbols\n represented as strings\n\n4. ``transitions``: a ``dict`` consisting of the transitions for each\n state; each key is a state name and each value is a ``dict`` which\n maps a symbol (the key) to a set of states (the values)\n\n5. ``initial_state``: the name of the initial state for this NTM\n\n6. ``blank_symbol``: a symbol from ``tape_symbols`` to be used as the\n blank symbol for this NTM\n\n7. ``final_states``: a ``set`` of final states for this NTM\n\n.. code:: python\n\n from automata.tm.ntm import NTM\n # NTM which matches all strings beginning with '0's, and followed by\n # the same number of '1's\n # Note that the nondeterminism is not really used here.\n ntm = NTM(\n states={'q0', 'q1', 'q2', 'q3', 'q4'},\n input_symbols={'0', '1'},\n tape_symbols={'0', '1', 'x', 'y', '.'},\n transitions={\n 'q0': {\n '0': {('q1', 'x', 'R')},\n 'y': {('q3', 'y', 'R')},\n },\n 'q1': {\n '0': {('q1', '0', 'R')},\n '1': {('q2', 'y', 'L')},\n 'y': {('q1', 'y', 'R')},\n },\n 'q2': {\n '0': {('q2', '0', 'L')},\n 'x': {('q0', 'x', 'R')},\n 'y': {('q2', 'y', 'L')},\n },\n 'q3': {\n 'y': {('q3', 'y', 'R')},\n '.': {('q4', '.', 'R')},\n }\n },\n initial_state='q0',\n blank_symbol='.',\n final_states={'q4'}\n )\n\nThe direction ``N`` (for no movement) is also supported.\n\nNTM.read_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nReturns a set of ``TMConfiguration``\\ s. These are basically tuples\ncontaining the final state the machine stopped on, as well as a\n``TMTape`` object representing the DTM\u2019s internal tape (if the input is\naccepted).\n\n.. code:: python\n\n ntm.read_input('01') # returns {TMConfiguration('q4', TMTape('xy..', 3))}\n\nCalling ``config.print()`` will produce a more readable output:\n\n.. code:: python\n\n ntm.read_input('01').pop().print()\n # q4: xy..\n # ^\n\n.. code:: python\n\n ntm.read_input('011') # raises RejectionException\n\nNTM.read_input_stepwise(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nYields sets of ``TMConfiguration``\\ s. Those are basically tuples\ncontaining the current state and the current tape as a ``TMTape``\nobject.\n\n.. code:: python\n\n ntm.read_input_stepwise('01')\n # yields:\n # {TMConfiguration('q0', TMTape('01', 0))}\n # {TMConfiguration('q1', TMTape('x1', 1))}\n # {TMConfiguration('q2', TMTape('xy', 0))}\n # {TMConfiguration('q0', TMTape('xy', 1))}\n # {TMConfiguration('q3', TMTape('xy.', 2))}\n # {TMConfiguration('q4', TMTape('xy..', 3))}\n\nNTM.accepts_input(self, input_str)\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\n.. code:: python\n\n if ntm.accepts_input(my_input_str):\n print('accepted')\n else:\n print('rejected')\n\nNTM.validate(self)\n^^^^^^^^^^^^^^^^^^\n\n.. code:: python\n\n ntm.validate() # returns True\n\nNTM.copy(self)\n^^^^^^^^^^^^^^\n\n.. code:: python\n\n ntm.copy() # returns deep copy of ntm\n\nBase exception classes\n~~~~~~~~~~~~~~~~~~~~~~\n\nThe library also includes a number of exception classes to ensure that\nerrors never pass silently (unless explicitly silenced). See\n``automata/base/exceptions.py`` for these class definitions.\n\nTo reference these exceptions (so as to catch them in a ``try..except``\nblock or whatnot), simply import ``automata.base.exceptions`` however\nyou\u2019d like:\n\n.. code:: python\n\n import automata.base.exceptions as exceptions\n\nclass AutomatonException\n^^^^^^^^^^^^^^^^^^^^^^^^\n\nA base class from which all other automata exceptions inherit (including\nfinite automata and Turing machines).\n\nclass InvalidStateError\n^^^^^^^^^^^^^^^^^^^^^^^\n\nRaised if a state is not a valid state for this automaton.\n\nclass InvalidSymbolError\n^^^^^^^^^^^^^^^^^^^^^^^^\n\nRaised if a symbol is not a valid symbol for this automaton.\n\nclass MissingStateError\n^^^^^^^^^^^^^^^^^^^^^^^\n\nRaised if a state is missing from the automaton definition.\n\nclass MissingSymbolError\n^^^^^^^^^^^^^^^^^^^^^^^^\n\nRaised if a symbol is missing from the automaton definition.\n\nclass InitialStateError\n^^^^^^^^^^^^^^^^^^^^^^^\n\nRaised if the initial state fails to meet some required condition for\nthis type of automaton.\n\nclass FinalStateError\n^^^^^^^^^^^^^^^^^^^^^\n\nRaised if a final state fails to meet some required condition for this\ntype of automaton.\n\nclass RejectionException\n^^^^^^^^^^^^^^^^^^^^^^^^\n\nRaised if the automaton stopped on a non-final state after validating\ninput.\n\nTuring machine exception classes\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\nThe ``automata.tm`` package also includes a module for exceptions\nspecific to Turing machines. You can reference these exception classes\nlike so:\n\n.. code:: python\n\n import automata.tm.exceptions as tm_exceptions\n\nclass TMException\n^^^^^^^^^^^^^^^^^\n\nA base class from which all other Turing machine exceptions inherit.\n\nclass InvalidDirectionError\n^^^^^^^^^^^^^^^^^^^^^^^^^^^\n\nRaised if a direction specified in this machine\u2019s transition map is not\na valid direction.\n\n.. |Build Status| image:: https://travis-ci.org/caleb531/automata.svg?branch=master\n :target: https://travis-ci.org/caleb531/automata\n.. |Coverage Status| image:: https://coveralls.io/repos/caleb531/automata/badge.svg?branch=master\n :target: https://coveralls.io/r/caleb531/automata?branch=master\n", "description_content_type": "", "docs_url": null, "download_url": "", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/caleb531/automata", "keywords": "automata turing machine", "license": "MIT", "maintainer": "", "maintainer_email": "", "name": "automata-lib", "package_url": "https://pypi.org/project/automata-lib/", "platform": "", "project_url": "https://pypi.org/project/automata-lib/", "project_urls": { "Homepage": "https://github.com/caleb531/automata" }, "release_url": "https://pypi.org/project/automata-lib/3.1.0.post1/", "requires_dist": null, "requires_python": "", "summary": "A Python library for simulating automata and Turing machines", "version": "3.1.0.post1" }, "last_serial": 4798337, "releases": { "1.0.0": [], "1.0.0.post1": [ { "comment_text": "", "digests": { "md5": "d51bf7a48e34593b22b38106a90f1770", "sha256": "459641308b939a2d250859e16195372174c1c54f9c639f0c4cc01a08a4285964" }, "downloads": -1, "filename": "automata-lib-1.0.0.post1.tar.gz", "has_sig": false, "md5_digest": "d51bf7a48e34593b22b38106a90f1770", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 7191, "upload_time": "2016-07-07T17:19:40", "url": "https://files.pythonhosted.org/packages/a5/1b/13008c82866fac6b18a77783aa8f0017634280c1aa2bc78a8f0aa2b2a13c/automata-lib-1.0.0.post1.tar.gz" } ], "1.0.0.post2": [ { "comment_text": "", "digests": { "md5": "a616a1077b0b88ed6c6ebd1a7aa003a9", "sha256": "02584e14b4a32cac43059123d8aa81cc99289f658d79804aa620c8e9cfce8a03" }, "downloads": -1, "filename": "automata-lib-1.0.0.post2.tar.gz", "has_sig": false, "md5_digest": "a616a1077b0b88ed6c6ebd1a7aa003a9", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 11662, "upload_time": "2016-07-07T20:18:51", "url": "https://files.pythonhosted.org/packages/a2/d1/4a5910ac8b3e22711551c7f1f54c96ac75b2c9cbc77253b9578a9e8b6c08/automata-lib-1.0.0.post2.tar.gz" } ], "1.0.0.post3": [ { "comment_text": "", "digests": { "md5": "ce622a90e2c39c106c7a24a3e5a6d809", "sha256": "b96f3d1bdf6c0ec75a423649845199fdd221a4cfb840cdb83d0e5867a2de1d05" }, "downloads": -1, "filename": "automata-lib-1.0.0.post3.tar.gz", "has_sig": false, "md5_digest": "ce622a90e2c39c106c7a24a3e5a6d809", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 11644, "upload_time": "2016-07-09T04:14:17", "url": "https://files.pythonhosted.org/packages/70/45/72b4ed5662fec40c38f5f37827fac0e1d6968beea1331eb9a8be7b9d64d5/automata-lib-1.0.0.post3.tar.gz" } ], "1.0.0.post4": [ { "comment_text": "", "digests": { "md5": "33e4557f1662dcd938579551369bc0dd", "sha256": "d3851f9a6437a596af87f6353306d1ce7a6f75a79eacf7ef3909a225b0021984" }, "downloads": -1, "filename": "automata-lib-1.0.0.post4.tar.gz", "has_sig": false, "md5_digest": "33e4557f1662dcd938579551369bc0dd", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 11634, "upload_time": "2017-05-02T04:15:21", "url": "https://files.pythonhosted.org/packages/85/a6/b33bb665852d62931130be77afd22f11b00b1e5e03faa2435a2367feeb16/automata-lib-1.0.0.post4.tar.gz" } ], "2.0.0": [ { "comment_text": "", "digests": { "md5": "539535155b2055293d4b19c4cdbc5322", "sha256": "b46f612cf6470095cb6856747bbe3f97904ac34b9e9ec94e1f6bf1d76d7b24a6" }, "downloads": -1, "filename": "automata-lib-2.0.0.tar.gz", "has_sig": false, "md5_digest": "539535155b2055293d4b19c4cdbc5322", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 10734, "upload_time": "2018-04-30T03:05:14", "url": "https://files.pythonhosted.org/packages/f4/f0/e8258ca65413c1c665a03076309bcb4a4192ba60e713dd9107b3af9cf10a/automata-lib-2.0.0.tar.gz" } ], "2.0.1": [ { "comment_text": "", "digests": { "md5": "1186105bf7b496b037946ddfbbe6d9c9", "sha256": "77c9775726e1e1ec8c20c5362f4be3d0baa8a148590923cd9630a1b5efcc9c27" }, "downloads": -1, "filename": "automata-lib-2.0.1.tar.gz", "has_sig": false, "md5_digest": "1186105bf7b496b037946ddfbbe6d9c9", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 10877, "upload_time": "2018-05-05T22:35:57", "url": "https://files.pythonhosted.org/packages/96/35/858f76ca86800a56d9965e68b320232fb6744df3da3814eefafbdb8691b3/automata-lib-2.0.1.tar.gz" } ], "2.1.0": [ { "comment_text": "", "digests": { "md5": "ad6294e18eca2e1099c9ff86f6be8fec", "sha256": "86e1bc896aa50189f23f1d851a6a8f028843b787a4a04e6912700843ca29b73e" }, "downloads": -1, "filename": "automata-lib-2.1.0.tar.gz", "has_sig": false, "md5_digest": "ad6294e18eca2e1099c9ff86f6be8fec", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 18305, "upload_time": "2018-05-29T02:46:38", "url": "https://files.pythonhosted.org/packages/88/34/cd50f6cfcf2459a6cca518116a110caf08074e8a96a4808b48ef42836f7d/automata-lib-2.1.0.tar.gz" } ], "3.0.0": [ { "comment_text": "", "digests": { "md5": "d1a8ca7abf97fe79eb6c9957f94a6a79", "sha256": "fdf62f0184ebe959b1f4a782d47852a86eccead8a9b45258bd86eecd161ecc17" }, "downloads": -1, "filename": "automata-lib-3.0.0.tar.gz", "has_sig": false, "md5_digest": "d1a8ca7abf97fe79eb6c9957f94a6a79", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 22791, "upload_time": "2019-01-21T04:22:02", "url": "https://files.pythonhosted.org/packages/4e/25/8bbe7fcabd0da99db9deb8c3378151aa649903dcdfa8bf9ce3219f25d15f/automata-lib-3.0.0.tar.gz" } ], "3.1.0": [ { "comment_text": "", "digests": { "md5": "973ab93a55de56320334e9f3bf056664", "sha256": "c00fd117f7adefa7db65ddd2e6361a5f8e7fe55950e0bfaf66d5ada148e8ed85" }, "downloads": -1, "filename": "automata-lib-3.1.0.tar.gz", "has_sig": false, "md5_digest": "973ab93a55de56320334e9f3bf056664", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 23200, "upload_time": "2019-02-09T03:44:27", "url": "https://files.pythonhosted.org/packages/25/46/68e7c2a91d02d26969e42ba752763a5520c842f865ea5151ee5d5ce1deb8/automata-lib-3.1.0.tar.gz" } ], "3.1.0.post1": [ { "comment_text": "", "digests": { "md5": "db0048fbe6e0749d2dc3832e6053a14d", "sha256": "b5673e92f88b16a9f0ea99b4c7e1048380077997480383bdd7db1346e4bd72f3" }, "downloads": -1, "filename": "automata-lib-3.1.0.post1.tar.gz", "has_sig": false, "md5_digest": "db0048fbe6e0749d2dc3832e6053a14d", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 23130, "upload_time": "2019-02-09T03:54:21", "url": "https://files.pythonhosted.org/packages/2e/7e/6dcd9d009fa9ffb7fa36f934b04684d7e343c544d986255a8d2f5cd00b1a/automata-lib-3.1.0.post1.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "db0048fbe6e0749d2dc3832e6053a14d", "sha256": "b5673e92f88b16a9f0ea99b4c7e1048380077997480383bdd7db1346e4bd72f3" }, "downloads": -1, "filename": "automata-lib-3.1.0.post1.tar.gz", "has_sig": false, "md5_digest": "db0048fbe6e0749d2dc3832e6053a14d", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 23130, "upload_time": "2019-02-09T03:54:21", "url": "https://files.pythonhosted.org/packages/2e/7e/6dcd9d009fa9ffb7fa36f934b04684d7e343c544d986255a8d2f5cd00b1a/automata-lib-3.1.0.post1.tar.gz" } ] }