5

反復補題を使用すると、その言語が正規言語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} + }は、次のことを意味します。

  • 文字列は、で構成される任意の文字列で開始する必要がaあります。bつまりW、逆文字列WRで終了します。
  • 注意： WとW Rは互いに逆であるため、文字列は同じ記号（またはのいずれaかb）で開始および終了します。
  • そして、との任意の文字列を含みます。（ので、の長さが1より大きくなります） abX+X|X| >= 1

この種の文字列の例は次のとおりです。

aabababa、次のように： 

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

またはそれはまたすることができます：

babababb、次のように： 

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

の長さはW言語定義の制約ではありません。

したがって、任意の文字列WXWRは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とWCWRを混在Xさせないでください+。これにより、言語が正規言語になります。Xそれを含めることによって、私たちはそれに対して有限の選択をすること(a + b)*ができると考えてください（有限は規則的です）。Wab

言語WXWRは、次のように言うことができます。で始まる場合はで終わり、で始まる場合はでa終わる。したがって、それに応じて2つの最終状態が必要です。abb

  • Q6Wの場合a
  • Q5Wの場合b

ITのDFAは以下のとおりです。

DFA

于 2013-01-26T07:26:49.933 に答える
2

|W|を含む言語の任意の文字列 > 1は、|W|の言語の文字列として解釈できます。= 1.したがって、文字列が同じ記号で始まり、同じ記号で終わる場合、文字列はその言語になります。aとbの2つの記号があります。そのため、その言語は言語と同等です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でなければなりません。現在、文字列a ^ n（a + b）a ^ nを受け入れるようなDFAはありません。これは、n個のaと（a + b）^ +を受け入れた後、dfaが正確にどのようにかを覚える方法がないためです。多くの人が最初に受け入れたので、L2は定期的であるべきではありません.........しかし、私がこの答えを検索するすべての場所で、それは定期的であると言います.....これは私を悩ませます

于 2013-02-02T13:38:44.013 に答える