5

使用pumping lemma，我们可以很容易地证明该语言L1 = {WcW^R|W ∈ {a,b}*}是正则语言。（字母表是{a,b,c}；W^R 代表逆向字符串W）

但是，如果我们用 替换字符c，"x"(x ∈ {a,b}+)比如说L2 = {WxW^R| x, W ∈ {a,b}^+}，，那么 L2是一种常规语言。

你能给我一些想法吗？

4

3 回答 3

14

如果我们将字符 c 替换为 x 其中 (x ∈ {a,b} + )，例如，L2 = {WXW R | x, W ∈ {a,b} + }，则 L2 是正则语言。

是的，L2是常规语言:)。

您也可以编写正则表达式L2。

语言 L2 = {WXW R | x, W ∈ {a,b} + } 表示：

  • string 应该以包含aand的任何字符串开头，b即W以反向字符串 W R结尾。
  • 注意：因为 W 和 W R是相反的，所以字符串以相同的符号开始和结束（可以是aor b）
  • 并在中间包含任何字符串和。（因为，长度变得大于一） abX+X|X| >= 1

这种字符串的示例如下：

aabababa，如下： 

   a    ababab    a  
  --   --------   --
   w     X        W^R

或者也可以是：

bababbabb，如下： 

   b    ababab    b
  --   --------   --
   w     X        W^R

请参阅长度W不是语言定义中的约束。

因此可以假定任何字符串 WXW R等于a(a + b)+a或b(a + b)+b

    a    (a + b)+   a
   ---   --------  ---
    W      X       W^R

或者

    b    (a + b)+   b
   ---   --------  ---
    W      X       W^R

这种语言的正则表达式是：a(a + b)++a + b(a + b)b

不要将WXWR与WCWRX混合使用，它+会使语言变得规则。X通过包含that is来思考(a + b)*我们可以有有限的选择that Wisa和b（有限是常规的）。

语言WXWR可以说： if start with aend with aand if start with bend with b。所以相应地我们需要两个最终状态。

  • Q6 如果W是a
  • Q5 如果W是b

它的 DFA 如下所示。

DFA

于 2013-01-26T07:26:49.933 回答
2

带有 |W| 的语言中的任何字符串 > 1 可以解释为语言中的字符串，其中 |W| = 1。因此，如果字符串以相同的符号开头和结尾，则该字符串属于该语言。有两个符号：a 和 b。所以说语言就等于语言a(a+b)(a+b)*a + b(a+b)(a+b)*b。为了证明这一点，您应该形式化“如果 y 在 WxW 中，则 y 在 a(a+b)(a+b)*a + b(a+b)(a+b)*b 中；并且如果 y 在 a(a+b)(a+b)*a + b(a+b)(a+b)*b 中，则 y 在 WxW 中”。

在另一种情况下它不起作用，因为 c 是一个固定符号，并且不能包含除末端字符之外的所有字符。一旦您在示例中绑定了“x”的长度，该语言就会变得非常规。

于 2013-01-25T18:28:23.693 回答
2

问题是 W ∈ {a,b}^+ ，所以 a^n(a+b)a^n 应该是 L2 语言。现在没有这样的 DFA 将接受字符串 a^n(a+b)a^n，因为在接受 n 个 a 和 (a+b)^+ 之后，dfa 无法准确记住如何一开始它接受了很多，所以L2不应该是常规的............但是我搜索这个答案的每个地方都说它是常规的......这让我很烦恼

于 2013-02-02T13:38:44.013 回答