明天考试,教授让我们知道一个问题:)。
在此图的上下文中,L 是 epsilon(空字符串),Z0 是堆栈空符号。
我在确定有关语言生成的单词的一些规则方面取得了一些进展,但无法确定整个语言。
谢谢!
最佳答案
该 PDA 几乎不像乍一看那样具有不确定性……请考虑以下情况。
ab
开头.然后我们用空栈进入状态2,所以“L”规则不匹配,所以我们只处于状态2。(a^n)b
开头对于 n > 1。然后我们使用 a^(n-1)
进入状态 2在堆栈上,“L”规则触发带我们回到状态 1 a^(n-2)
在堆栈上。但是由于状态 2 中的堆栈是 a^(n-1)
(并且 n>1),状态 2 上的环回箭头无法匹配......所以再次,我们(实际上)仅处于一种状态:状态 1。ba
开头.然后我们再次进入状态 2,堆栈为空,与情况 (1) 一样,“L”规则不匹配,因此我们仅处于状态 2。(b^n)a
开头对于 n > 1。然后我们使用 b^n
进入状态 2在堆栈上,所以“L”规则不会触发,我们只处于状态 2。换句话说,任何时候“L”规则将 PDA 的“ fork ”创建为状态 1,它只会这样做,因为“a”在堆栈顶部......这意味着保持状态 2 的 fork 必须死在下一个输入符号上。因此,实际上这里没有不确定性,您可以对这个 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
s 合作”。状态 1,堆栈 = a^n
表示 n a
s正在等待合作伙伴。状态 1,堆栈 = b^n
表示 n b
s正在等待合作伙伴。状态 2,堆栈 = b^n
表示一个 b
与一位合伙人 a
和 n b
s还在等待合作伙伴。证明我刚才写的是真的,结果如下。
关于context-free-grammar - 这个下推自动机 (PDA) 接受什么语言?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7018113/