pushdown-automaton - 具有不等变量的下推自动机

Question

我无法想出一个正确的自动机来成功接受以下内容:

当然是由任意数量的 {a, b, c}* 以任意顺序组成的字符串，但是 n(a) + n(b) != n(c)

最初，我已指定将“x”压入任何“a”或“b”的堆栈中，并在遇到“c”时从堆栈中删除“x”。这将根据需要在两个状态之间循环。当然，如果 a 和 b 之前有任意数量的 c，情况就会变得复杂。我显然无法从空堆栈中删除。欢迎任何想法或建议!

Answer 1

这款 PDA 并不简单。您必须使用两个分支(一个用于增量(A 和 B)，一个用于减量(C))。诀窍是放置一个堆栈顶部标记并查找该标记。如果你按下它，请坚持(不要在你的乐队上走得更远)切换分支并在你的分支上推负片。

下面我通过三元组定义转换:(输入、弹出、推送)

例如:

1. (A,ϵ,#) 表示:从输入中读取 A，不弹出任何内容，将 # 压入堆栈
2. (ϵ,#,B) 表示:什么也不读(停在实际位置，这一步不再继续)，pop #，push B
3. (AB,ϵ,X) 表示:读取 A 或 B 并推送 X

举个例子:

S = starting state
Q1 = "switch branches" state, from here the stack is empty and we move in the branch we need in dependend of the next character read from the input band.
Q2, Q3 = States of the there-is-an-A-or-B-next branch
Q4, Q5 = States of the there-is-a-C-next branch
Q6 = State of acceptance (the only one. all other states are not accepting)

现在过渡:

S -(ϵ,ϵ,#)-> Q1 ' # is our top-of-the-stack-marker

' first branch (for more As and Bs)
Q1 -(AB,ϵ,+)-> Q2 ' for every A or B push a + sign on the stack
Q2 -(AB,ϵ,+)-> Q2
Q2 -(C,+,ϵ)-> Q3 ' for every C consume a + sign
Q3 -(AB,ϵ,+)-> Q2
Q3 -(C,+,ϵ)-> Q3
Q3 -(ϵ,#,#)-> Q1 ' if we reach the top of the stack, return to the Q1 state
Q2 -(ϵ,#,#)-> Q1
Q2 -($,+,+)-> Q6 ' if the input is processed and the stack is not empty => go in the state of acceptance
Q3 -($,+,+)-> Q6 ' if the input is processed and the stack is not empty => go in the state of acceptance

' second branch (for more Cs)
Q1 -(C,ϵ,-)-> Q4 ' for every C push a - sign on the stack
Q4 -(C,ϵ,-)-> Q4
Q4 -(AB,-,ϵ)-> Q5 ' for every A or B consume a - sign
Q5 -(AB,-,ϵ)-> Q5
Q5 -(C,ϵ,-)-> Q4
Q5 -(ϵ,#,#)-> Q1
Q4 -(ϵ,#,#)-> Q1
Q4 -($,-,-)-> Q6 ' if the input is processed and the stack is not empty => go in the state of acceptance
Q5 -($,-,-)-> Q6 ' if the input is processed and the stack is not empty => go in the state of acceptance

逻辑描述:

我们在堆栈上压入 # 符号来检测堆栈顶部。 现在我们在两个“区域”运营。与 C 相比，第一个区域处理正数的 A 和 B，另一个区域处理与 C 相比负数的 As 和 B。

我们正在使用属于堆栈一部分的三个标志:

1. '# = 顶部标记
2. '+ = 读取的 A 和 B 数量多于 C 数量
3. '- = 读取的 C 多于 As 或 B

第一次转换是从起始状态到新的起始状态。此转换仅用于将顶部标记插入堆栈的原因。永远不会再次达到新的原始起始状态。 新的起始状态是 switch，每次我们点击堆栈上的顶部标记时都会点击它。从这个状态开始，我们将访问依赖于下一个 A 和 B 或 C 的区域。

我希望这能解释它。所描述的自动机应该会给您一个好主意。我认为其中有一点错误，但如果你遵循这个想法并且你做对了，那么你可以修复它:)

我用在线模拟器构建了所描述的自动机来测试它。可以找到here 。这个模拟器使用 epsilon 作为输入带的初始化并且不执行任何操作......所以它有点令人困惑。我添加了一些测试，可以通过单击“批量测试”旁边的绿色箭头来运行这些测试。