【緊急】{ww: w∈{a, b}*}はRegular language?

質問

{ww: w∈{a, b}*}はRegular languageですよね?
{ww^R: w∈{a, b}*}はNon-regular languageというのは知っています。

さっき試験が終わったばっかりで気になって仕方がありません。

回答No.2

hpsk · ベストアンサー

> という場合がありえますが
－－－－－－－－－－＊＊ 最後のa..ab、
を忘れていました。どっちにしても結論はかわりませんが、訂正します。

あと、ついでなので１つアドバイス的なことを。
正規表現の能力の限界は、直観的には、DFAが有限の状態しか持たないということに起因します。
例えば、(^i )^i（＝同じ数の対応する括弧）が正規表現で表せないことはご存知ですよね。
これは、「(^i が入力された時点で、今までに何個の( が入力されたかを覚えておく必要があるが、それは有限の状態では不可能だから」と理解することができます。

こう理解しておくと、証明するまでもなく、{ww: w∈{a, b}*} は正規言語ではないということが予想できるかと思います。

お礼

さっき試験が返ってきました。
当然×でした、とほほ。

(^i )^iは今まで見たことありませんでした。
試験前に知っておけばよかったです。
ありがとうございました。

回答No.1

hpsk

残念ながら（？）、{ww: w∈{a, b}*} も Non-regular です。
これは、{ww^R: w∈{a, b}*}が Non-regular であることの証明とほぼ同じように示すことが出来ます。

あまり厳密な証明ではないですが、簡単に説明すると・・・

{ww: w∈{a, b}*}を受理するDFAが存在したとすると、
このDFAは、(a^n)b(a^n)b という記号列を受理するはずです（a^nはaのn個の並び）。

DFAの状態数は有限なので、nがある一定以上大きくなると記号列長が状態数を超えます。
そのような記号列を受理するためには、必ずDFA中の同じ状態を2度通る必要があります。つまり、
Sk → ... → Sk
という遷移のループがDFAに必ず存在します。

(a^n)b(a^n)bを受理した際、このループで処理した記号列は、
ａ．．．ａｂａ．．．ａｂ のうち、
－＊＊＊－－－－－－－－ このあたりか（前半のa)、
－－－－＊＊＊－－－－－ このあたりか（a...aba...a、または前後のaを含まない場合）、
－－－－－－－＊＊＊－－ このあたりか（後半のa)、
－－－－－－－－－－－＊ 最後のbだけ、
という場合がありえますが（多分表示がずれますが、だいたいわかりますよね）、
このうちのどれであったとしても、このようなループが存在すると、このDFAは{ww: w∈{a, b}*} に含まれない記号列も受理できることになってしまいます。

これは矛盾であり、{ww: w∈{a, b}*}を受理するDFAは存在せず、つまり{ww: w∈{a, b}*}は正規言語ではない、ということになります。