ある言語クラス判定問題(正規言語?文脈自由言語?)

質問

形式言語に関する以下の問題に悩んでおります。

問題:
Lを正規言語とするとき、以下の言語L1, L2はそれぞれ(1)-(5)のどれに該当するか?

L1={xy | xとyは共にLの元で、長さが同じ(|x|=|y|, x in L, y in L)}
L2={xy | xとyは共にLの元で、xの長さはyの長さの2倍(|x|=2|y|, x in L, y in L)}

(1)正規言語である
(2)正規言語ではないが、文脈自由言語である
(3)文脈自由言語ではないが、文脈依存言語である
(4)文脈依存言語ではないが、帰納的可算言語である
(5)帰納的可算言語ではない

直観的には(有限オートマトンは数を数えられないので)L1もL2も正規言語ではないと思うのですが、私の力では証明することが出来ないでおります。
ヒントや部分的回答(e.g. ひとまず(1)ではない。理由はかくかくしかじか)でもありがたいですので、どうぞよろしくお願いいたします。

回答No.3

Tacosan

あ, できたできた.
#1 の通り, 「L に依存して (1) か (2)」であってる.
たかだか文脈自由であることは, #1 で書いたように NPDA を作ってもいいし, L を与える文法から L1 や L2 を与える文脈自由文法が作れることを示してもいい.
正規にならないことがあるってのは, 素直に「適当な L に対して作った L1 や L2 が正規言語に対する反復補題を満たさない」ことを示す.

お礼

Tacosan様、ご教示ありがとうございます。

具体的な証明作成を頑張ります。

回答No.2

Tacosan

お, #1 の文章は変だ. 「なんとなく」ではじまる文は
「どんな L に対しても L1 や L2 は非決定性PDA で受理できる」かつ「L1 や L2 が正規でない L が存在する」ような気がする
という意味でとってください.

お礼

Tacosan様

補足の書き込みをありがとうございます。
了解いたしました。

回答No.1

Tacosan

まず問題を確認したいのですが, L によって複雑さは変わると考えられますよね. 例えば L = { a } なら, L1 も L2 も明らかに正規です. ということで, (1)～(5) に分類するためには
・L を限定する
・「任意の L に対して高々どのくらいの複雑さなのか」を答える
のどちらかでないとまずいんですけど, どうなんでしょうか?
なんとなく非決定性PDA で受理できそうかつ正規ではなさそう (つまり (2) である) な気がするんだけどなぁ. というわけで以下思いつき:
「非決定性PDA で受理できる」というのは, L を受理する有限オートマトンをベースにして L1 や L2 を受理する非決定性PDA を作る. 「回文の集合が文脈自由」の証明が参考になりそう.
逆に「正規ではない」というのは反復補題を使うのが標準的な手法だと思います. つまり, 適当な L から L1 や L2 を作って, それらが反復補題を満たさないことが示せればいい.
たぶんこれでいけると思うけど, 細部はつめてないので抜けがあるかも知れません.

お礼

Tacosan様、今回もご教示をありがとうございます。

題意としては
>・「任意の L に対して高々どのくらいの複雑さなのか」
こちらでお願いいたします。きちんと書かずに申し訳ありませんでした。

いただいたヒントを元に証明を考えてみます。