1

我正在为非上下文无关语言 L={a^(n)b^(n)c^(n)|n>=1} 构建一个下推自动机，并想到了两种方法。

第一种方法：-

我认为对于字符串中的每个“a”，我会将 3 个“a”推入堆栈，对于字符串中的每个“b”，我现在将为字符串中的每个“c”从堆栈中弹出 2 个“a”我堆栈中仍会有 1 个“a”。

第一种方法的问题：-生成的语言变成这样 L={a^(p)b^(m)c^(n)| p>=1 并且无法确定如何定义 m 和 n }

第二种方法：-

我们知道 L={ a^(n)b^(m)c^(m)d^(n) | n>=0 } 是上下文无关语言，L={ wxw | w∈(a,b)* } 也是上下文无关语言。

所以，我认为 L={ a^(n)b^(m)b^(m)c^(n) | n>=1 和 m=floor((n+1)/2) }

第二种方法的问题：-不知道我们是否可以在不干扰堆栈元素的情况下在 PDA 中计算 floor(n+1/2)。

请帮助确定如何在第一种方法中定义 m 和 n 以及如何在 PDA 中找到 floor((n+1)/2) 。

如果需要，两者都可以使用 JFLAP 文件。

4

2 回答 2

1

您没有设法为这种语言构建下推自动机的一个原因是因为没有。Bar Hillel 泵引理说明了这一点。

为了概述证明，假设它可以完成。然后，对于某些p，每个大于p的字符串都可以划分为uvwxy、 st 、

  • |vwx| < p

  • |vx| > 1

  • uv n wx n y也被自动机接受，对于任何n。

第一条规则意味着vwx不能跨越三个区域，最多只能跨越两个（对于足够大的字符串）。第二条和第三条规则现在意味着您可以抽水，以使未跨越的区域小于其他区域中的至少一个。

于 2016-10-29T15:11:28.530 回答
1

正如 Ami Tavory 指出的那样，这种语言没有 PDA，因为这种语言不是上下文无关的。如果您使用队列而不是堆栈、使用两个堆栈或使用图灵机（均等效），则很容易识别这种语言。

排队机：

  1. a只要看到s就将s 排入队列a，直到看到 a 为止b。
  2. Dequeue as 和 enqueue bs 只要你看到bs，直到你看到一个c
  3. b只要你看到s就将s 出列c。
  4. 如果您在没有额外输入和空队列的情况下结束此过程，请接受。

两栈PDA：

  1. 使用第一个堆栈来确保在看到 an时a^n b^n按下并在看到 a 时弹出；aaab
  2. 使用第二个堆栈来确保在看到 a 时b^n c^n按下并b在看到 a时b弹出；bc
  3. 如果在此过程结束时两个堆栈都为空，则接受。

图灵机：

  1. a^n ... c^n通过将每个替换a为A并删除匹配来确保c；
  2. A^n b^n通过擦除匹配的A和来确保b；
  3. 如果在此过程结束时您没有更多A和没有更多，则接受b，即磁带已被完全清除。
于 2016-11-02T12:34:56.183 回答