プッシュダウンオートマトンについて

from collections import namedtuple

class PDARule(namedtuple('PDARule', ['start_state', 'character', 'next_state', 'popped_char', 'pushed_chars'])):
    '''
    Transition rule of pushdown automaton.
    This class is immutable.
    '''
    __slots__ = ()

    def is_applied_to(self, char, state, stack):
        '''
        Return True if this rule can be applied to the passed condition of PDA.
        '''
        if char is not None:
            return char == self.character and \
                    state == self.start_state and \
                    stack[-1] == self.popped_char
        else:
            return self.character is None and \
                    state == self.start_state and \
                    stack[-1] == self.popped_char

    def apply(self, char, state, stack):
        '''
        Apply this rule and calculate a next state and stack.
        '''
        if not self.is_applied_to(char, state, stack):
            raise RuntimeError('cannot apply the rule: %s' % (str(self)))
        next_state = self.next_state
        next_stack = list(stack)
        next_stack.pop()
        next_stack += reversed(self.pushed_chars)
        return (next_state, next_stack)

class DPDA:
    '''
    Simulator of deterministic pushdown automaton.
    '''
    def __init__(self, initial_state, rules, accept_states):
        self.initial_state = initial_state
        self.rules = rules
        self.accept_states = accept_states

    def does_accept(self, string):
        '''
        Return True if a passed string is in the language of this automaton.
        '''
        state = self.initial_state
        index = 0
        stack = ['$'] # '$' means the bottom of stack
        while index < len(string):
            if not self.has_available_rules(string[index], state, stack):
                return False
            state, stack = self.transit(string[index], state, stack)
            index += 1
        return state in self.accept_states

    def collect_available_rules(self, char, state, stack):
        return [ rule for rule in self.rules if rule.is_applied_to(char, state, stack) ]

    def has_available_rules(self, char, state, stack):
        return len(self.collect_available_rules(char, state, stack)) > 0

    def transit(self, char, state, stack):
        available_rules = self.collect_available_rules(char, state, stack)
        if len(available_rules) == 0:
            raise RuntimeError('cannot transit since this DPDA is in the stuck state')
        # apply a rule (this is deterministic, so there should be only one available rule)
        rule = available_rules[0]
        next_state, next_stack = rule.apply(char, state, stack)
        # epsilon moving if necessary, which consumes no input.
        if self.has_available_rules(None, next_state, next_stack):
            return self.transit(None, next_state, next_stack)
        else:
            return (next_state, next_stack)

if __name__ == '__main__':
    # Transition rules to accept strings consisting of correct pairs of '(' and ')'.
    transition_rules = (
            PDARule(1, '(' , 2, '$', ['b', '$']),
            PDARule(2, '(' , 2, 'b', ['b', 'b']),
            PDARule(2, ')' , 2, 'b', []),
            PDARule(2, None, 1, '$', ['$']),
            )
    # Simulator of DPDA
    dpda = DPDA(1, transition_rules, {1})
    assert dpda.does_accept('') == True
    assert dpda.does_accept('(())') == True
    assert dpda.does_accept('(()())') == True
    assert dpda.does_accept('(()') == False
    assert dpda.does_accept('(()))') == False