automation - 我怎样才能说出常规语言？

Question

众所周知，使用抽引引理，我们可以很容易地证明语言L = {WW|W ∈ {a,b}*}不是正则语言。

然而，语言，L1 = {W1W2| |W1| = |W2|} 是一种常规语言。因为我们可以像下面这样得到 DFA，

我的问题是，L = {WW|W ∈ {a,b}*}也有偶数长度的字符串（|w|=|w|，绝对），L 仍然可以有一些像上面那样的 dfa。怎么不是普通语言？

谢谢。

Answer 1

您误解了语言ww，而语言DFA是 L1：

[问题]：

• L ={ ww| w = w}是正则语言(RL)。因为我们可以得到DFA像下面这样是可能的。

  DFA:  L1 ={ w1w2| |w1| = |w2|, where w1 , w2 ∈ {a, b}* } 
  
  --►((even))------a,b---------►(odd)  
        ▲                         |  
        |--------a,b--------------| 
  

[怀疑]

什么是L ={ ww | w ∈ {a, b}* } 是哪里？

L 是由偶数长度字符串组成的a，b即有一些前缀子字符串等于后缀子字符串。一些例子L是{ aa, bb, abab, aaaa, bbbb, abaaba, abbabb, .....}

DFA或 L1的语言是什么 ={ w1w2| |w1| = |w2|，其中 w1 , w2 ∈ {a, b}* } ？

所有偶数长度的a字符串都由b例如L1{ab, ba, aabb, baab, ab, aa, bb, ababa, baba, abbba, ...}

注意： 所有偶数长度的字符串都包含a并且b不在L例如{ab, ba, aabb, baab, ab}，但是这个字符串在DFA's language = L1.

所以，L(DFA)=L1 != L

[疑问-1]

L和之间的关系L(DFA)=L1？

正如我在注释中所写的，L ⊆ L(DFA)因此属于LDFA 语言元素的每个字符串都接受了您DFA。（这是你的困惑）

此外，语言L ={ ww| |w| = |w| } 不是常规语言。我们不能DFA为这种语言绘图。两种语言都不一样！(L != L1)

L那时受到很大限制L(DFA)

L={ WW|W }不规则可以使用抽引引理证明。

_{L甚至不是上下文无关语言，而是上下文相关语言}

Answer 2

我在 cs.stackexchange 中发布了这个主题，Ran 为我提供了答案。https://cs.stackexchange.com/questions/9175/how-come-ww-isnt-regular-when-uv-uv-is

两种语言的主要区别是第一种语言不需要记住它的内容仅仅计算长度就足够了，而第二种语言需要分析 w 和 w 是否相同。

谢谢@Ran、@Grijesh 和@dema80 :-)