时间戳

首页 > 解决方案 > How can I write pushdown automata?

algorithm - How can I write pushdown automata?

问题描述

Starting with the letter b and the number of the letters b is 1 more than the number of the letters a a PDA that accepts language

It confused me a lot. Can anyone explain how it's done?

标签： algorithmpushdown-automaton

解决方案

PDA 可以用这些属性定义（使用Wikipedia上提出的语法）：

  • 状态： {， ， }
  • 输入字母：{, }
  • 堆栈字母：{, , }
  • 开始状态：
  • 开始堆栈符号：
  • 接受状态：{}

过渡：

状态 输入 堆栈顶部 新州 堆顶变化
∈</td>
∈</td>
∈</td>

这个想法是 PDA 仅在状态时接受输入。在那种情况下，状态将变为 。

在 state 中，当输入为 且栈顶不是 时，将被压入栈中。同样当输入 ，而栈顶不是 时，则会被压入栈中。所以堆栈永远不能混合 和 。

当输入符号为 且栈顶为 时，则从栈中弹出。同样，当输入为 且栈顶为 时，则从栈中弹出。

最后的转换表明 PDA 可以从状态转换到栈顶时。

如果输入可以完全被这些规则处理，并且状态可以变为 ，则输入被接受。否则不行。

在代码中，算法大致是这样工作的（这是 Python）：

def run(input):
    state = "r"
    stack = ["Z"]
    for ch in input:
        if state == "r" and ch == "b" and stack[-1] == "Z":
            state = "s"
        elif state == "s" and ch == "a" and stack[-1] == "Z":
            stack.append("a")
        elif state == "s" and ch == "b" and stack[-1] == "Z":
            stack.append("b")
        elif state == "s" and ch == "a" and stack[-1] == "a":
            stack.append("a")
        elif state == "s" and ch == "b" and stack[-1] == "b":
            stack.append("b")
        elif state == "s" and ch == "a" and stack[-1] == "b":
            stack.pop()
        elif state == "s" and ch == "b" and stack[-1] == "a":
            stack.pop()
        else:
            return False  # Input is rejected as there is no matching transition

    if state == "s" and stack[-1] == "Z":
        state = "t"
    return state == "t"  # Accepting when, and only if, the state is "t"
    
run("baaabbb")  # True
run("aaabbbb")  # False

推荐阅读