形式言語に関する以下の問題に悩んでおります。
問題:
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)ではない。理由はかくかくしかじか)でもありがたいですので、どうぞよろしくお願いいたします。
A 回答 (3件)
- 最新から表示
- 回答順に表示
No.2
- 回答日時:
お, #1 の文章は変だ. 「なんとなく」ではじまる文は
「どんな L に対しても L1 や L2 は非決定性PDA で受理できる」かつ「L1 や L2 が正規でない L が存在する」ような気がする
という意味でとってください.
No.1
- 回答日時:
まず問題を確認したいのですが, L によって複雑さは変わると考えられますよね. 例えば L = { a } なら, L1 も L2 も明らかに正規です. ということで, (1)~(5) に分類するためには
・L を限定する
・「任意の L に対して高々どのくらいの複雑さなのか」を答える
のどちらかでないとまずいんですけど, どうなんでしょうか?
なんとなく非決定性PDA で受理できそうかつ正規ではなさそう (つまり (2) である) な気がするんだけどなぁ. というわけで以下思いつき:
「非決定性PDA で受理できる」というのは, L を受理する有限オートマトンをベースにして L1 や L2 を受理する非決定性PDA を作る. 「回文の集合が文脈自由」の証明が参考になりそう.
逆に「正規ではない」というのは反復補題を使うのが標準的な手法だと思います. つまり, 適当な L から L1 や L2 を作って, それらが反復補題を満たさないことが示せればいい.
たぶんこれでいけると思うけど, 細部はつめてないので抜けがあるかも知れません.
Tacosan様、今回もご教示をありがとうございます。
題意としては
>・「任意の L に対して高々どのくらいの複雑さなのか」
こちらでお願いいたします。きちんと書かずに申し訳ありませんでした。
いただいたヒントを元に証明を考えてみます。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
素数の性質
-
3,4,7,8を使って10を作る
-
実息とは?
-
よって・ゆえに・したがって・∴...
-
数学の「証明」のときなどの接...
-
(4^n)-1が3の倍数であることの...
-
再婚、奨学金
-
無理数って二乗しても有理数に...
-
証明終了の記号。
-
婿養子に入ったのに出て行けと...
-
中学校の2年生に仮定と結論を...
-
婿養子です、妻と離婚して妻の...
-
素数の積に1を加算すると素数で...
-
正の整数a.b.cが a^2+b^2=c^2を...
-
「証明証」と「証明書」はどう...
-
数学の証明問題で、「証明終了」...
-
σ集合体の証明
-
背理法を使うとき
-
正解が一つとは限らない数学の...
-
再婚を考えてますが、養子縁組...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
数学の「証明」のときなどの接...
-
数学の証明問題で、「証明終了」...
-
夫が亡くなった後の義理家族と...
-
よって・ゆえに・したがって・∴...
-
婿養子です、妻と離婚して妻の...
-
√2が無理数であることの証明で...
-
証明終了の記号。
-
素数の性質
-
婿養子に入ったのに出て行けと...
-
3,4,7,8を使って10を作る
-
無理数って二乗しても有理数に...
-
(4^n)-1が3の倍数であることの...
-
素数の積に1を加算すると素数で...
-
素数の平方根は無理数である。
-
親の再婚相手との問題です。私...
-
「証明証」と「証明書」はどう...
-
下の問題では漸化式の形から≠0...
-
47歳、母親の再婚を子供の立場...
-
ぶすですか?
-
直角三角形の性質
おすすめ情報