class NTM(TM)

Classes and methods for working with nondeterministic Turing machines.

NTM

Bases: TM

The NTM class is a subclass of TM and represents a nondeterministic Turing machine.

Parameters:

Name	Type	Description	Default
states	AbstractSet[NTMStateT]	A set of the NTM's valid states.	required
input_symbols	AbstractSet[str]	Set of the NTM's valid input symbols, each of which is a singleton string.	required
tape_symbols	AbstractSet[str]	Set of the NTM's valid tape symbols, each of which is a singleton string.	required
transitions	NTMTransitionsT	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 tuples consisting of the next state, the symbol to write on the tape, and the direction to move the tape head.	required
initial_state	NTMStateT	The name of the initial state for this NTM.	required
blank_symbol	str	A symbol from tape_symbols to be used as the blank symbol for this NTM.	required
final_states	AbstractSet[NTMStateT]	A set of final states for this NTM.	required

Example

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'}
)

read_input_stepwise(input_str)

Check if the given string is accepted by this Turing machine.

Yield the current configurations of the machine at each step.

Parameters:

Name	Type	Description	Default
input_str	str	The input string to read.	required

Yields:

Type	Description
Generator[Set[TMConfiguration], None, None]	A generator that yields the current configuration of the NTM after each step of reading input.

Raises:

Type	Description
RejectionException	Raised if this NTM does not accept the input string.

validate()

Raises an exception if this automaton is not internally consistent.

Raises:

Type	Description
InvalidStateError	If this NTM has invalid states in the transition dictionary.
InvalidSymbolError	If this NTM has invalid symbols in the transition dictionary.
InvalidDirectionError	If this NTM has a transition with an invalid direction.
FinalStateError	If this NTM has a transition on any final states.