【お知らせ】まとめて検索などの提供終了

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

問題:
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)ではない。理由はかくかくしかじか)でもありがたいですので、どうぞよろしくお願いいたします。

このQ&Aに関連する最新のQ&A

A 回答 (3件)

あ, できたできた.


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

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

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

お礼日時:2010/04/06 08:03

お, #1 の文章は変だ. 「なんとなく」ではじまる文は


「どんな L に対しても L1 や L2 は非決定性PDA で受理できる」かつ「L1 や L2 が正規でない L が存在する」ような気がする
という意味でとってください.
    • good
    • 0
この回答へのお礼

Tacosan様

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

お礼日時:2012/05/19 11:46

まず問題を確認したいのですが, L によって複雑さは変わると考えられますよね. 例えば L = { a } なら, L1 も L2 も明らかに正規です. ということで, (1)~(5) に分類するためには


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

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

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

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

お礼日時:2010/04/06 07:43

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q大学院別のTOEICの合格点を教えてください。

大学院入試でTOEICの点数を英語の点数として換算している大学院が多くあると知ったのですが大学院別にどのぐらいが合格点なのでしょうか?
東大の院生の平均点が730というデータはネットでみたのですが他のいろいろな大学院について教授からや友達からの情報でもいいので参考にさせてください。

Aベストアンサー

このサイトに、大学院入試でTOEIC(R)Testを活用する52の大学院が、
国公立、私立別で掲載されており、
ある一定のスコアで、英語の独自試験免除など、詳しい情報が見れます!

参考URL:http://www.toeicclub.net/graduateschool.html

Q2進数において、3の倍数になる規則は?

10進数では全ての桁の和が3の倍数になればいい
では2進数において3の倍数になる規則はなんでしょうか。

逆に3進数において2の倍数になる規則はなんでしょうか。
後者は1の個数が偶数。
でいいですか?

前者についてはなかなか手法がみつかりません。。

Aベストアンサー

No.2です。

> 10^1 ≡ 10 ≡ -1 (mod 11)
> の式に現れる数は全て2進表記ですよね?

その通りです。

> 10^2 ≡ (10)^2 ≡100(4のこと)≡ 1(4を3で割るとあまりは1)  (mod 11)
> と考えていいですか?

その通りです。

Q研究室訪問せずに出願。先方を怒らせました・・・・

 現在、理系の4年です。今年、他大学を受験します。本命の研究室には、以前研究室訪問したのですが、第二志望(独立系で4年がいない。)には研究室訪問せずに出願しました。
 
 その際、事前に連絡を入れるという条件だったので、連絡したところ、先方が研究室訪問せずに出願したことを非常に心配しておられ、試験終了後に一度研究室に伺うように連絡を頂きました。本命の方が合格したら、辞退しなければならないので研究室訪問は行はなかったのでが・・・
 
 これで、合格を辞退したら、さらに、失礼なことになりそうです。とにかく、本命の方を受かるように、努力しますが・・・なんとか角がたたず研究室訪問をできるにはどうしたら良いでしょうか?本命と併願していることをご説明した方が良いでしょうか?
 

 私は研究室訪問の際は、(合否がでていないため)お話だけはしっかり聞いて、本命が落ちたら進学して、合格してたら、詳しくお話をうかがったらどうもやりたい事とは違った云々といい辞退するつもりですが・・・ 不味くはないでしょうか?


 ご回答お願いいたします。

Aベストアンサー

アメリカ在住です。数年前まで某国公立大学で大学院を指導していました。

 先方の立場になってみましょう。指導する立場からすると,いろいろウソや話していないことがある学生はイヤなものです。院生は戦力ですから,実際に自分の下で頑張ってもらうことになります。それが「いやじつは,」という話しばかりでは困りますよね。素直な学生さんは本当にいい仕事をしますし,良い業績を残すと思います。

 大学院時代はいつも良いことばかりではありません。どう頑張ってもデータが出ないこともあります。そのときに辛抱強く頑張って,正直に進めるかはとても大切です。もしも変なことをしてデータをいじったり,論文をかえたりすると教室の信用問題になります。個人的には「正直」でないひとはお引き取り願っています。

 同じ学会で第一志望と第二志望の教室の先生と会うかもしれません。狭い世界ですから。その時どうしますか?ウソから始まると話しがずれたりして,どうしても上手く行かないものです。学問の世界で生きたいのに最初から学会に行きづらい,会いたくない先生がいるというのはどう考えてもマイナスです。

>内容はホームページで確認したので、大丈夫かと思っていました。
これは非常に問題ある選び方です。その教室の論文は読んでみましたか?最新の論文でもアクセプト,出版まで半年から1年かかりますから,それだけ前の研究であると言うことです。ましてHPでは何年前の研究かわかりません。あとは言葉に出来ない雰囲気も大切です。

 どの様な人数構成になっていますか?指導するのは教授,助教授,講師,助手?チームは何チーム?雑用は?就職の実績やその後の方向性は?それは志望を決めるのに大事な要素ですが,今のcyandorerさんの場合はなにも知らず,相手の印象もあまり良くはないでしょう。

 感覚的には大学院選びは結婚に近いのですが,今回は「あなたが相手の数年前のお見合い写真だけ見て,会わずに相手にいきなり入籍を迫った」ようなものです。第2志望だとしても,相手にもあなたを知ってもらう必要があります。今後同じフィールドで働く先生に「変な学生が来た」とだけ思われて終わるか(すでに手順を端折っており,現段階ではそう思われている可能性があります),「素晴らしい学生だけど残念ながら別の大学に行ってしまうんだな」と思われるのでは大違いです。ちなみにアメリカはとても人柄を見ます。業績がいい人は山ほどいますが,チームとして動けるかどうかを非常に重く見ます。最初から人脈を壊す方向は良くありません。

ご参考になりましたら幸いです。

アメリカ在住です。数年前まで某国公立大学で大学院を指導していました。

 先方の立場になってみましょう。指導する立場からすると,いろいろウソや話していないことがある学生はイヤなものです。院生は戦力ですから,実際に自分の下で頑張ってもらうことになります。それが「いやじつは,」という話しばかりでは困りますよね。素直な学生さんは本当にいい仕事をしますし,良い業績を残すと思います。

 大学院時代はいつも良いことばかりではありません。どう頑張ってもデータが出ないこともあります。そ...続きを読む


人気Q&Aランキング