形式言語に関する以下の問題に悩んでおります。
問題:
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で質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語のエラーについて 2 2022/07/11 13:56
- 英語 ソシュール言語観による品詞、単語、辞書理解の誤り 4 2022/11/24 12:27
- システム科学 オートマトン、文脈自由文法の問題 2 2023/07/12 23:19
- 中学校 口語自由詩・文語自由詩について 3 2023/05/29 11:52
- 英語 仮主語の「to be+名詞」の和訳について 4 2022/05/07 14:49
- 日本語 意味とは何か? どこにあるのか?(Ⅱ) 4 2022/04/21 13:35
- 日本語 <代名詞><指示詞>という誤り 4 2022/04/01 11:06
- 高校 テスト勉強について 中間テストの結果がかえってきたのですがあまりよくありませんでした。 現代の国語と 2 2023/06/05 00:46
- 哲学 日本語は 言語類型として あたかも始原のごとくである 3 2022/05/29 04:41
- 英語 ちょっと細かいんですが、前から考えてて、 However, it was less successf 2 2022/11/03 23:37
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
有理数と無理数が無限個あること
-
証明終了の記号。
-
数学の「証明」のときなどの接...
-
rankに関する証明問題です。
-
数学の証明問題で、「証明終了」...
-
無理数って二乗しても有理数に...
-
よって・ゆえに・したがって・∴...
-
素数の性質
-
じゃらんで旅行予約をしたので...
-
原始関数の存在性の証明につい...
-
兄弟の子どもの養子縁組は可能...
-
巡回群と巡回群の直積は巡回群?
-
liman=a(n→∞)、limbn=b(n→∞)な...
-
婿養子です、妻と離婚して妻の...
-
大学の二次試験で・・・
-
次元定理以外で
-
「証明証」と「証明書」はどう...
-
夫が亡くなった後の義理家族と...
-
数学Aの整数の性質について質問...
-
心霊漫画家で新興宗教団体の教...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
数学の「証明」のときなどの接...
-
3,4,7,8を使って10を作る
-
証明終了の記号。
-
婿養子に入ったのに出て行けと...
-
数学の証明問題で、「証明終了」...
-
「証明証」と「証明書」はどう...
-
素数の積に1を加算すると素数で...
-
夫が亡くなった後の義理家族と...
-
よって・ゆえに・したがって・∴...
-
学割定期を親に買ってきてもら...
-
(4^n)-1が3の倍数であることの...
-
再婚、奨学金
-
素数の性質
-
なぜ独身だと養子が持てないの...
-
元夫が彼女の存在を隠す理由
-
成人した後両親が離婚し別の人...
-
大学の給付型奨学金について 現...
-
直角三角形の性質
-
通学証明書の契印とは
-
無理数って二乗しても有理数に...
おすすめ情報