利用抽头引理,我们可以很容易地证明语言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 是一种常规语言。
你能给我一些想法吗?
发布于 2013-01-25 18:28:23
在语言中,任何字符串都可以被解释为以相同符号开头和结尾的语言中的字符串,在这种语言中,一个字符串以相同的符号开头和结尾。有两个符号: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-02-02 13:38:44
问题是W {a,b}^+,所以a^n(a+b)a^n应该在L2语言中。现在没有这样的DFA来接受字符串a^n(a+b)a^n,因为在接受了a和(a+b)^+的n个数后,dfa无法准确记住它在开始时接受了多少a,所以L2不应该是regular.........But,因为我在搜索这个答案时,它说是regular.....this困扰着我。
https://stackoverflow.com/questions/14521300
复制相似问题