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, ...}

注: すべての偶数長の文字列は、たとえば言語 = L1 の 文字列aでbはなく、この文字列で構成されています。L{ab, ba, aabb, baab, ab}DFA

それで、L(DFA)=L1 != L

[疑問-1]

LとL(DFA)=L1の 関係

注記に書いたように、DFA の言語の要素L ⊆ L(DFA)にも属し、すべての文字列が受け入れられます。（これはあなたの混乱です） LDFA

また、言語L ={ ww| |w| = |w| } は正規言語ではありませんDFA。この言語では絵を描くことはできません。両方の言語が同じではありません!(L != L1)

Lその場合は非常に制限されていますL(DFA)

L= { WW|W }is not regular は、ポンピング補題を使用して証明できます。

_{Lまた、文脈自由言語ではなく、文脈依存言語でもあります}

Answer 2

私はこのtheadをcs.stackexchangeに投稿し、Ranが答えを提供してくれます。https://cs.stackexchange.com/questions/9175/how-come-ww-isnt-regular-when-uv-uv-is

2つの言語の主な違いは、最初の言語では長さを計算するためだけに内容を覚えておく必要がないのに対し、2番目の言語ではwとwが同一であるかどうかを分析する必要があることです。

@ Ran、@ Grijesh、@dema80に感謝します:-)