class NPDA(PDA)

Classes and methods for working with nondeterministic pushdown automata.

NPDA

Bases: PDA

The NPDA class is a subclass of PDA and represents a nondeterministic pushdown automaton.

Parameters:

Name	Type	Description	Default
states	AbstractSet[NPDAStateT]	A set of the NPDA's valid states	required
input_symbols	AbstractSet[str]	Set of the NPDA's valid input symbols, each of which is a singleton string.	required
stack_symbols	AbstractSet[str]	Set of the NPDA's valid stack symbols, each of which is a singleton string.	required
transitions	NPDATransitionsT	A dict consisting of the transitions for each state; see the example below for the exact syntax	required
initial_state	NPDAStateT	The name of the initial state for this NPDA.	required
initial_stack_symbol	str	The name of the initial symbol on the stack for this NPDA.	required
final_states	AbstractSet[NPDAStateT]	A set of final states for this NPDA.	required
acceptance_mode	PDAAcceptanceModeT	A string defining whether this NPDA accepts by 'final_state', 'empty_stack', or 'both'.	'both'

Example

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', '#')},  # no change to stack
            },
            'a': {
                '#': {('q0', ('A', '#'))},  # push 'A' to stack
                'A': {
                    ('q0', ('A', 'A')),  # push 'A' to stack
                    ('q1', ''),  # pop from stack
                },
                'B': {('q0', ('A', 'B'))},  # push 'A' to stack
            },
            'b': {
                '#': {('q0', ('B', '#'))},  # push 'B' to stack
                'A': {('q0', ('B', 'A'))},  # push 'B' to stack
                'B': {
                    ('q0', ('B', 'B')),  # push 'B' to stack
                    ('q1', ''),  # pop from stack
                },
            },
        },
        'q1': {
            '': {'#': {('q2', '#')}},  # push '#' to (currently empty) stack
            'a': {'A': {('q1', '')}},  # pop from stack
            'b': {'B': {('q1', '')}},  # pop from stack
        },
    },
    initial_state='q0',
    initial_stack_symbol='#',
    final_states={'q2'},
    acceptance_mode='final_state'
)

read_input_stepwise(input_str)

Return a generator that yields the configuration of this NPDA at each step while reading input.

Parameters:

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

Yields:

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

Raises:

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