用代码实现下推自动机

下面是一个简单的 Python 代码实现下推自动机，用来判断字符串是否是形如 a^n b^n 的语言：

class PDA:
    def __init__(self, input_str):
        self.input_str = input_str
        self.stack = []
        self.current_state = 0
        self.accept_states = {3}
        self.transitions = {
            (0, 'a', ''): (1, 'a$'),
            (1, 'a', 'a'): (1, 'aa'),
            (1, 'b', 'a'): (2, ''),
            (2, 'b', 'a'): (2, ''),
            (2, '', '$'): (3, '')
        }

    def is_accepted(self):
        for c in self.input_str:
            if (self.current_state, c, self.peek()) not in self.transitions:
                return False
            next_state, push = self.transitions[(self.current_state, c, self.peek())]
            if push != '':
                self.push(push)
            self.current_state = next_state
        return self.current_state in self.accept_states

    def peek(self):
        if len(self.stack) == 0:
            return ''
        else:
            return self.stack[-1]

    def push(self, value):
        self.stack.append(value)

pda = PDA('aaaabbbb')
print(pda.is_accepted()) # True

pda = PDA('aaabbb')
print(pda.is_accepted()) # False

在这个实现中，PDA 用一个字典来存储状态转移关系。键是一个三元组 (current_state, input_symbol, stack_top)，值是一个二元组 (next_state, stack_push)，表示当当前状态为 current_state，输入符号为 input_symbol，栈顶符号为 stack_top 时，进行转移到 next_state，将 stack_push 压入栈顶。

在 is_accepted 方法中，我们读取输入字符串中的每个字符，查找是否存在与当前状态、输入符号、栈顶符号匹配的状态转移，如果找到了就进行转移，并将符号压入栈中。最后检查最终状态是否在接受状态中即可。

这个 PDA 实现是比较简单的，但是可以作为理解下推自动机的一个基础。