4

明天考试，教授让我们知道一个问题:)。

在该图的上下文中，L 是 epsilon（空字符串），Z0 是堆栈空符号。

我在确定有关该语言生成的单词的一些规则方面取得了一些进展，但无法确定整个语言。

谢谢！

掌上电脑图

4

3 回答 3

4

这个 PDA 并不像乍一看那样具有不确定性……请考虑以下情况。

  1. 假设输入以 开头ab。然后我们带着空栈进入状态 2，所以“L”规则不匹配，所以我们只处于状态 2。

  2. 假设输入以(a^n)bn > 1 开始。然后我们a^(n-1)在堆栈上进入状态 2，并且“L”规则触发将我们带回到a^(n-2)堆栈上的状态 1。但是由于状态 2 中的堆栈是a^(n-1)（并且 n>1），状态 2 上的环回箭头无法匹配......所以在这里，我们（实际上）只处于一种状态：状态 1。

  3. 假设输入以 开头ba。然后我们再次进入状态 2，堆栈为空，与情况 (1) 一样，“L”规则不匹配，因此我们仅处于状态 2。

  4. 最后，假设输入以(b^n)an > 1 开始。然后我们进入状态 2，堆栈上的 with b^n，因此“L”规则不会触发，我们仅处于状态 2。

换句话说，任何时候“L”规则在状态 1 中创建 PDA 的“分叉”，它这样做只是因为“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 as 合作”。状态 1，stack=a^n表示 n as 正在等待合作伙伴。状态 1，stack=b^n表示 n bs 正在等待合作伙伴。状态 2，stack=b^n表示一个b与一个合作，a 并且n bs 仍在等待合作伙伴。

证明我刚才写的是真的，结果如下。

于 2011-08-11T02:06:11.940 回答
2

在我的脑海中玩一些测试用例并且没有严格证明任何东西，我认为当且仅当输入字符串的 a's 数量是 b's 数量的两倍时，这个（非确定性）PDA 存在一个可接受的计算。

于 2011-08-10T22:00:15.703 回答
1

“a”的数量是“b”数量的两倍。

准确语法：

S  = (a|b)*      where N_a(S)=2*N_b(S)

N_a(X) 表示 X 中 'a' 的数量等。

在任何时间点，堆栈都可以是全 a 或全是 b。为什么？因为，没有 a/xxbxx 或 b/xxaxx 的转换。

情况 1：堆栈全是 'a'。

您可以看到循环的形式为：

  1. a(a*b)+ ，如果最后我们采用 (2->1) 中的转换 L,a/L

  2. a(a*b)+a，如果最后我们采用 (2->1) 中的转换 a,Z0/Z0。最后一个'a'不会从堆栈中弹出任何东西。

在每个循环中，弹出的 'a' 数量为 2。并且循环数与“b”数相同（最后出现a，Z0 / Z0时除外）

如果“a”的数量甚至在最后一个“b”之前，我们将采用最后一个转换 L,a/L

如果“a”的数量在最后一个“b”之前是奇数，我们将采用最后一个转换 a,Z0/Z0。a,Z0/Z0 再接受一个 'a'

因此，

A1=a(a*b)+a  where N_a(A1)=2*N_b(A1),     N_a(A1) is even
A2=a(a*b)+   where N_a(A2)=2*N_b(A2),     N_a(A2) is even

这将减少到：

A=a(a|b)+    where N_a(A)=2*N_b(A),     N_a(A) is even

（我们将处于状态 1，堆栈为空）

情况 2：堆栈全是 'b'。

同样，您可以看到每个循环的形式为：b*ab*a。并且在每个循环中，都会弹出一个“b”。每当接受“b”时，就会将“b”压入堆栈。因此，当堆栈为空并且我们回到状态 1 时，循环的次数等于我们接受/推入堆栈的 'b' 的数量。因此，

B=b(b*ab*a)^n where N_b(B)=n

但是你可以看到，n = N_a(B)/2。因此，

B=b(b*ab*a)+ where N_a(B)=2*N_b(B)

这将减少到：

B=b(b|a)+ where N_a(B)=2*N_b(B)

并且由于只有两条可能的路径（A 或 B），并且循环可以取 0 次或 1 次，

因此，

S=(A|B)*
A=a(a|b)+    where N_a(A)=2*N_b(A)
B=b(b|a)+    where N_a(B)=2*N_b(B)

这将减少到：

S=((a|b)+)*   where N_a(S)=2*N_b(S)

这将减少到：

S=(a|b)*      where N_a(S)=2*N_b(S)

量子点

于 2011-08-11T00:07:16.900 回答