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 回答