class MNTM(TM)

Classes and methods for working with multitape nondeterministic Turing machines.

MNTM

Bases: NTM

The MNTM class is a subclass of TM and represents a multitape (non)deterministic Turing machine.

Parameters:

Name	Type	Description	Default
states	AbstractSet[MNTMStateT]	A set of the MNTM's valid states.	required
input_symbols	AbstractSet[str]	Set of the MNTM's valid input symbols, each of which is a singleton string.	required
tape_symbols	AbstractSet[str]	Set of the MNTM's valid tape symbols, each of which is a singleton string.	required
n_tapes	int	The number of tapes in this MNTM.	required
transitions	MNTMTransitionsT	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 list 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	MNTMStateT	The name of the initial state for this MNTM.	required
blank_symbol	str	A symbol from tape_symbols to be used as the blank symbol for this MNTM.	required
final_states	AbstractSet[MNTMStateT]	A set of final states for this MNTM.	required

Example

from automata.tm.mntm import MNTM
# MNTM which accepts all strings in {0, 1}* and writes all
# 1's from the first tape (input) to the second tape.
self.mntm1 = MNTM(
    states={'q0', 'q1'},
    input_symbols={'0', '1'},
    tape_symbols={'0', '1', '#'},
    n_tapes=2,
    transitions={
        'q0': {
            ('1', '#'): [('q0', (('1', 'R'), ('1', 'R')))],
            ('0', '#'): [('q0', (('0', 'R'), ('#', 'N')))],
            ('#', '#'): [('q1', (('#', 'N'), ('#', 'N')))],
        }
    },
    initial_state='q0',
    blank_symbol='#',
    final_states={'q1'},
)

read_input_as_ntm(input_str)

Simulates this MNTM as a single-tape Turing machine. Yields the configuration at each step.

Parameters:

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

Yields:

Type	Description
Generator[AbstractSet[TMConfiguration], None, None]	A generator that yields the current configuration of the MNTM as a set after each step of reading input.

Raises:

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

read_input_stepwise(input_str)

Checks if the given string is accepted by this MNTM machine, using a BFS of every possible configuration from each configuration. Yields the current configuration 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[MTMConfiguration], None, None]	A generator that yields the current configuration of the DTM after each step of reading input.

Raises:

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

validate()

Raises an exception if this automaton is not internally consistent.

Raises:

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