该下推自动机 (PDA) 接受什么语言？
明天考试，教授会让我们知道其中的一个问题:)。
在此图中，L 是 epsilon（空字符串），Z0 是堆栈空符号。
我在确定有关该语言生成的单词的一些规则方面取得了一些进展，但未能确定整个语言。
谢谢！
Exam tomorrow and the prof let us know a question that would be on it :).
In the context of this diagram, L is epsilon (The empty string), and Z0 is the stack empty symbol.
I've made some progress in determining a few rules about the words the language generates, but haven't been able to pin down the entire language.
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这个 PDA 并不像乍一看那样具有不确定性......考虑以下情况。
假设输入以
ab开头。然后我们进入状态 2，堆栈为空，因此“L”规则不匹配，因此我们仅处于状态 2。假设输入以
(a^n)b 开头对于n> 1. 然后我们进入状态 2，a^(n-1)在堆栈上，“L”规则触发，将我们带回到状态 1，a^(n-2) )在堆栈上。但是由于状态 2 中的堆栈是a^(n-1)（并且 n>1），状态 2 上的环回箭头无法匹配...所以这里再次，我们（有效地） ) 仅在一种状态：状态 1。假设输入以
ba开头。然后我们再次进入状态 2，堆栈为空，与情况 (1) 一样，“L”规则不匹配，因此我们仅处于状态 2。最后，假设输入以
( 开头b^n)a对于 n > 1. 然后我们进入状态 2，其中b^n在堆栈上，因此“L”规则不会触发，我们仅处于状态 2。换句话说，任何时候“L”规则都 不会触发。 “规则创建 PDA 的一个“分叉”进入状态 1，它这样做只是因为“a”位于堆栈顶部......这意味着保持在状态 2 的分叉必须在下一个输入符号处消失。因此，实际上这里不存在非确定性，您可以对该 PDA 进行建模，就好像它始终处于一种状态一样。
有了这个观察，我认为很容易看出@Nayuki 是正确的：这个 PDA 接受任何 a 的数量是 b 的两倍的字符串。
首先，表明当 PDA 处于状态 1 时，堆栈总是完全由 a 或完全由 b 组成（或者为空）。当 PDA 处于状态 2 时，堆栈完全由 b 组成（或者为空）。这是一个与上面四个案例类似的简单案例分析；例如“状态1，堆栈=a^n，下一个字符b=>状态1，堆栈=a^(n-2)”。 （注意 n=0 或 n=1 的情况。）
将每个
b视为“想要与 2 个a合作”。状态 1，stack=a^n表示 n 个a正在等待伙伴。状态 1，stack=b^n表示 n 个b正在等待伙伴。状态 2，stack=b^n表示一个b与一个a和 nb 合作仍在等待合作伙伴。证明我刚才写的是真的，结果如下。
This PDA is not nearly as non-deterministic as it appears at first glance... Consider the following cases.
Suppose the input starts with
ab. Then we go to state 2 with an empty stack, so the "L" rule does not match, so we are only in state 2.Suppose the input starts with
(a^n)bfor n > 1. Then we go to state 2 witha^(n-1)on the stack, and the "L" rule triggers taking us back to state 1 witha^(n-2)on the stack. But since the stack in state 2 isa^(n-1)(and n>1), the loop-back arrows on state 2 cannot match... So here again, we are (effectively) only in one state: state 1.Suppose the input starts with
ba. Then again we go to state 2 with an empty stack, and as in case (1), the "L" rule does not match so we are only in state 2.Finally, suppose the input starts with
(b^n)afor n > 1. Then we go to state 2 with withb^non the stack, so the "L" rule does not trigger and we are only in state 2.In other words, any time the "L" rule creates a "fork" of the PDA into state 1, it only does so because "a" was on top of the stack... Which implies that the fork remaining in state 2 must die on the very next input symbol. So in effect there is no non-determinism here, and you can model this PDA as if it is always in just one state.
With this observation in hand, I think it is pretty easy to see that @Nayuki is correct: This PDA accepts any string with twice as many a's as b's.
First, show that when the PDA is in state 1, the stack always consists entirely of a's or entirely of b's (or is empty). And when the PDA is in state 2, the stack consists entirely of b's (or is empty). This is a simple case analysis similar to the four cases above; e.g. "state 1, stack=a^n, next character b => state 1, stack=a^(n-2)". (Taking care for the cases of n=0 or n=1.)
Think of each
bas "wanting to be partnered with 2as". State 1, stack=a^nmeans nas are waiting for partners. State 1, stack=b^nmeans nbs are waiting for partners. State 2, stack=b^nmeans onebwas partnered with oneaand nbs are still waiting for partners.Prove that what I just wrote is true, and the result follows.
在我脑子里玩了一些测试用例并且没有严格证明任何东西，我认为当且仅当输入字符串的 a 数量是 a 数量的两倍时，这个（非确定性）PDA 才存在可接受的计算。 b 的。
Playing with some test cases in my head and not proving anything rigorously, I think there exists an accepting computation for this (non-deterministic) PDA if and only if the input string has twice the number of a's compared to the number of b's.
“a”的数量是“b”数量的两倍。
精确语法：
N_a(X) 表示 X 中“a”的数量等。
在任何时间点，堆栈都可以是全“a”或全“b”。为什么？因为，没有 a/xxbxx 或 b/xxaxx 的转换。
情况 1：堆栈全是“a”。
您可以看到循环的形式为：
a(a*b)+ ，如果最后我们在 ( 2->1)
a(a*b)+a，如果最后我们进行过渡a，(2→1)中的Z0/Z0。最后一个“a”不会从堆栈中弹出任何内容。
在每个循环中，弹出的“a”数量为两个。并且循环数与“b”的数量相同（除非a，Z0 / Z0最后出现），
我们将采用最后一个转换L，a / L当且仅当“a”的数量在最后一个“b”之前
如果“a”的数量在最后一个“b”之前是奇数，我们将采用最后一个转换 a,Z0/Z0。 a,Z0/Z0 又接受一个 'a'
因此，
这将减少为：（
我们将处于状态 1，并且堆栈为空）
情况 2：堆栈全部为 'b'。
同样，您可以看到每个循环的形式为：b*ab*a。
在每个循环中，恰好有一个“b”会被弹出。
每当“b”被接受时，“b”就会被推入堆栈。
因此，当堆栈为空时，我们回到状态 1，循环的次数等于我们接受/推入堆栈的 'b' 的数量。因此，
但是您可以看到，n = N_a(B) /2。因此，
这将减少为：
由于只有两条可能的路径（A 或 B），并且循环可以进行 0 或 1 次，
因此，
这将减少为：
这将减少为：
QED
Number of 'a' is twice the number of 'b's.
Exact Grammar:
N_a(X) means Number of 'a's in X. etc.
At any point in time, the stack can either be all 'a's or all 'b's. Why? because, there are no transitions of a/xxbxx or b/xxaxx.
Case 1: Stack is all 'a's.
You can see cycle will be of the form:
a(a*b)+ , if last we take the transition L,a/L in (2->1)
a(a*b)+a, if last we take the transition a,Z0/Z0 in (2->1). and the last 'a' will not pop anything from stack.
in each cycle, the number of 'a's popped are two. and number of cycle is same as number of 'b' (except when a,Z0/Z0 occured at the last)
we'll take the last transition L,a/L iff number of 'a' is even before last 'b'
we'll take the last transition a,Z0/Z0 iff number of 'a' is odd before last 'b'. a,Z0/Z0 accepts one more 'a'
Thus,
This will reduce to:
(we'll be state 1, and stack empty)
Case 2: Stack is all 'b's.
Similarly, you can see that each cycle will be of the form: b*ab*a.
and in each cycle, exactly one 'b' will be popped off.
Whenever a 'b' is accepted, a 'b' is pushed onto the stack.
Thus when the stack is empty, and we're back to state 1, number of times the cycle is taken is equal to number of 'b's we accepted/pushed onto stack.Thus,
But you can see, n = N_a(B)/2. Thus,
This will reduce to:
And since there are only two possible paths (A or B), and the cycle can be taken 0 or 1 times,
Thus,
This will reduce to:
which will reduce to:
Q.E.D.