- 締切済み
ある言語クラス判定問題(正規言語?文脈自由言語?)
形式言語に関する以下の問題に悩んでおります。 問題: 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)ではない。理由はかくかくしかじか)でもありがたいですので、どうぞよろしくお願いいたします。
- 数学・算数
- 回答数3
- ありがとう数6
- みんなの回答 （3）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
あ, できたできた. #1 の通り, 「L に依存して (1) か (2)」であってる. たかだか文脈自由であることは, #1 で書いたように NPDA を作ってもいいし, L を与える文法から L1 や L2 を与える文脈自由文法が作れることを示してもいい. 正規にならないことがあるってのは, 素直に「適当な L に対して作った L1 や L2 が正規言語に対する反復補題を満たさない」ことを示す.
- Tacosan
- ベストアンサー率23% (3656/15482)
お, #1 の文章は変だ. 「なんとなく」ではじまる文は 「どんな L に対しても L1 や L2 は非決定性PDA で受理できる」かつ「L1 や L2 が正規でない L が存在する」ような気がする という意味でとってください.
お礼
Tacosan様 補足の書き込みをありがとうございます。 了解いたしました。
- Tacosan
- ベストアンサー率23% (3656/15482)
まず問題を確認したいのですが, L によって複雑さは変わると考えられますよね. 例えば L = { a } なら, L1 も L2 も明らかに正規です. ということで, (1)～(5) に分類するためには ・L を限定する ・「任意の L に対して高々どのくらいの複雑さなのか」を答える のどちらかでないとまずいんですけど, どうなんでしょうか? なんとなく非決定性PDA で受理できそうかつ正規ではなさそう (つまり (2) である) な気がするんだけどなぁ. というわけで以下思いつき: 「非決定性PDA で受理できる」というのは, L を受理する有限オートマトンをベースにして L1 や L2 を受理する非決定性PDA を作る. 「回文の集合が文脈自由」の証明が参考になりそう. 逆に「正規ではない」というのは反復補題を使うのが標準的な手法だと思います. つまり, 適当な L から L1 や L2 を作って, それらが反復補題を満たさないことが示せればいい. たぶんこれでいけると思うけど, 細部はつめてないので抜けがあるかも知れません.
お礼
Tacosan様、今回もご教示をありがとうございます。 題意としては >・「任意の L に対して高々どのくらいの複雑さなのか」 こちらでお願いいたします。きちんと書かずに申し訳ありませんでした。 いただいたヒントを元に証明を考えてみます。
関連するQ&A
- 言語理論の文脈自由言語について
「オートマトン 言語理論 計算論Ｉ」という本（教科書）を読んでいます。 この本には演習問題がついているのですが、本を読んだだけでは解法が分らない上、 答えがついてないため、解けない問題が多く困っています。 （連休明けに試験があり、その範囲なんです。） ある言語が文脈自由型ででないことを証明したいのですが、 反復補題（パンピングレンマ）を用いて背理法によるのだろうと思うのですが、 どのように仮定するかの方針が立たないのです。 具体的には次のような問題に対し、「…」のような仮定をしてみました。 ａ）｛ａ＾ｉ ｂ＾ｊ ｃ＾ｋ ｜ ｉ＜ｊ＜ｋ｝ 「ｚ＝ａ＾ｎ ｂ＾（ｎ＋ｌ） ｃ＾（ｎ＋ｍ） （但し、ｍ＞ｌ＞０）」 しかし、下記のように背理法による矛盾が示せなかったのです。 どこで間違ったのかは分らないので、間違った個所を指摘していただきたいのです。 よろしくお願いします。 「言語を文脈自由言語と仮定する。 ｎをパンピングレンマの性質を持つ整数とし、 ｚ＝ａ＾ｎ ｂ＾（ｎ＋ｌ） ｃ＾（ｎ＋ｍ） （但し、ｍ＞ｌ＞０）とすると、 ｚ∈Ｌ かつ ｜ｚ｜≧ｎ が成立する。 したがって、パンピングレンマから ｚ＝ｕ ｖ ｗ ｘ ｙ （ｕｘ≠ε、｜ｖｗｘ｜≦ｎ） と表され、かつ ｕ ｖ＾ｉ ｗ ｘ＾ｉ ｙ ∈ Ｌ が成立する。 ｜ｖｗｙ｜≦ｎ なので、ｖｘがａとｃの両方を含むことはない。 ｖｘのパターンにより次の２つの場合を考える （ｉ）ｖｘが一種類の文字だけからなる場合 … （ｉｉ）ｖｘが２種類の文字からなる場合」 ここまで書いたところで、 ｖ＝ｂ、ｘ＝ｃ とすると、例えば、 ｕ＝ａ、ｗ＝ｂｂ、ｙ＝ｃｃｃ の場合を考えると、矛盾が導けないことに気付きました。
- ベストアンサー
- 科学
- 正規言語に対する繰り返し定理による証明
正規言語に対する繰り返し定理による証明 L={w|wは0と1を同じ個数含む}とする。 Lが正規言語でないことを、繰り返し定理を用いて証明せよ。 【繰り返し定理】 1.|y|>0 2.|xy|≦n 3.∀i≧0,xy^izはLの部分集合 言語Lが正規言語であると仮定すると、Lに対して繰り返し定理が成立する。 Lに属する語A=w(wは0と1をn個ずつ含む)をとると、|A|=2n≧nであるから、定理の条件を満たすようなAの分解A=xyzが存在する。 この後をどうすればよいのかが分かりません。 yが (0の個数)=(1の個数)のとき (0の個数)>(1の個数)のとき (0の個数)<(1の個数)のとき で場合分けをすればいいとは思うのですが・・・ どう矛盾を導きだせばいいのかが分かりません。 ご教授願います。
- 締切済み
- 数学・算数
- 二次元正規分布に関連する問題に困っています．
二次元正規分布に関連する問題に困っています． xy平面上に10×10の100個の格子があり， そのそれぞれの格子がzの値として， 1から100のいずれかの値を持っています． 与えられる点のイメージは以下のようになります． (x,y,z)=(1,1,56) (x,y,z)=(1,2,57) (x,y,z)=(1,3,59) … (x,y,z)=(100,100,98) zの値はxy平面上にランダムに散らばっているのではなく， 波の様なある曲面に沿って散らばっています． 今この局面上に散らばった値をもとに， z=55.55 という値が最も存在し得る位置を求めます． 現在のところ自分の考えではz=55.55という値と， 散らばった100個のzの値との偏差を計算し， この100個の偏差が最小となる点が， 最もz=55.55の点が存在し得るということを考えました． ここで，相関係数ρ=0とした二次元正規分布， f(x,y)=1/(2pi*σx*σy) *exp( -1/2 * ( (x-μx)^2/σx^2 + (y-μy)^2/σy^2 ) ) というf(x,y)を導入して， 上で考えたz=55.55という値が最も存在し得る位置を求めたいです． どなたか確率分布に詳しい方がいらっしゃいましたら， アドバイスをよろしくお願いいたします．
- ベストアンサー
- 数学・算数
- あせってます！！因数分解分かる方教えて
因数分解が分かりません。。。解き方と公式あれば詳しく教えて下さい。問）Xｙ＋X－２ｙー２ 問）X（２乗）ｙ－４Xｙ＋３ｙの２問答えと共によろしくお願いします。
- ベストアンサー
- 数学・算数
- 有限オートマトンの限界
文系の大学生ですが理系の学問も少しかじっていますが、全くわからないのです。 とくに教科書の有限オートマトンにかんするこの記述がよくわかりません 「有限状態機械で定義できる言語はかなり限定されている。 ab,aabb,aaabbb,・・・ のように文字aがn個続いた後、n個の文字bが現れるような文字列からなる 言語を定義することが出来ません」 え・・・なんでできないんですか・・・？そのあと文脈自由文法なら正規文法で書けなかったab,aabb,aaabbbのパターンの定義も書ける、と書いてあるのですが、それもよくわかりません。こんなオバカですけど、どうしても理解したいので、説明よろしくおねがいします！m(._.)mちなみにとても急いでいます！よろしくおねがいします！！
- ベストアンサー
- 科学
- R言語に関わる確率変数の問題についてです。
Rの関数によるプログラミング関係についての質問です。次の問題が分からないのでどなたか教えていただけませんか。 確率変数Ｘ、Ｙは正規分布Ｎ(0,1)，Ｎ(1,4)に従っている。つぎの値をＲの 関数を使って答えよ。 (a) p1=Ｐ(Ｘ≦1) (b) p2=Ｐ(Ｘ＞1) (c) p3=Ｐ(Ｙ≦1) (d) Ｐ(Ｘ≦α)=0.95となるα (e) 自由度15のt分布に従う確率変数ＺについてＰ(Ｚ≦β)=0.99となるβ
- 締切済み
- 数学・算数
- 正規表現とオートマトンについての問題です。
正規表現とオートマトンについての問題です。 下記の決定性有限オートマトンMが受理する言語L（M)を正規表現で表したい。以下のカタカナ に入る記述を穴埋めしなさい。 状態iから状態ｊに、kより大きな数字の状態を通らないで遷移させる入力文字列の集合をkRij と表すと、一般的に、 kRij = k-1Rik(k-1Rkk)*k-1Rkj∪k-1Rijと表される。 そこで、L(M)とは、初期状態1から受理状態3へ3より大きな数字の状態を通らないで遷移させる 入力文字列の集合のことであるから、 L(M) = ア = 2R13(2R33)*2R33∪2R13 ・・・・・(1) と書ける。(1)式は2R13でくくると、 L(M) = 2R13((2R33)*イ∪ウ) ・・・・・(1') となるが、一般に文字列集合をAとするとき、 A* = エ∪A1∪A2∪A3∪ ・・・ と定義され、 A*A = (オ∪A1∪A2∪A3∪ ・・・ )A = A1∪A2∪A3∪A4∪ ・・・ となり、 従って、A*A∪{ε} = A*A ∪ A0 = A* ・・・・・(2) である。よって(1')式は、 L(M) = 2R13(2R33)* ・・・・・(1'') と簡単化される。(1'')式の、まず2R13を求める。 2R13 = カ(1R22)*キ∪1R13 ここで、ク = 0R11(0R11)*0R12∪0R12 = {ε}{ε}*{1}∪ケ = コ 1R22 = 0R21サ0R12∪0R22 = シ{ε}*{1}∪{ε,1} = {ε,1} 1R23 = 0R21(0R11)*0R13∪0R23 = φ{ε}*ス∪{0} = {0} 1R13 = 0R11(0R11)*0R13∪セ = {ε}ソ{0}∪タ = チ 故に 2R13 = ツ{ε,1}*{0}∪テ ここで、{ε,1}* = トだから 2R13 = {1}ナ{0}∪{0} = ({1}ニ∪{ε}){0} ・・・・・(3) 次に2R33については 2R33 = ヌ(1R22)*1R23∪1R33 ここで、 ネ = 0R31ノ0R12∪0R32 = φ{ε}*{1}∪φ = ハ 1R33 = 0R31(0R11)*0R13∪0R33 = φ{ε}*{0}∪{ε,ヒ} = {ε,フ} 故に 2R33 = φ{ε,1}*{0}∪{ε,0}=ヘ 従って(1'')式は、(3)(4)式から L(M) = ({1}ホ∪{ε}){0}{ε,0}* 上式()内は(2)式と同様の理由からマであり、{ε,0}* = ミであるから L(M) = ム{0}メ これを正規表現すれば L(M) = モ0ヤ となる。 -----答え----- ア=3R13 イ=? ウ=? エ=A^0 オ=A^0 カ=1R12 キ=1R23 ク=1R12 ケ={1} コ={1} サ=(0R11)* シ=φ ス={0} セ=0R13 ソ={ε}* タ={0} チ={0} ツ={1} テ={0} ト=? ナ=? ニ=? ヌ=1R32 ネ=1R32 ノ=(0R11)* ハ=φ ヒ=0 フ=0 エ=?ホ=?マ=?ミ=?ム=?メ=?モ=?ヤ=? 途中までは解けたんですが?の箇所がわかりません・・・ よろしくお願いします。
- ベストアンサー
- 情報工学
- ラグランジュ乗数法について質問です
初歩的な質問ですみません。 経済学を習っている時にでラグランジュ未定乗数法が出てきたのですが、 U=xy+y m=2x+y でxとyの関数を求めるために L=xy+x+λ(m-2x-y)とすると教科書に書いてありました。(このあとx,y,λで偏微分していきます) この時、Uはどこに行ってしまったのでしょうか。 求めたいものを、Lとおくのでしょうか。 もちろん経済学は置いといてくださって大丈夫です。 数学としてどうなっているのか、教えていただけないでしょうか？
- ベストアンサー
- 数学・算数
- 数学的帰納法~整数であることの証明
数学的帰納法の初歩(?)の質問です。 問。ｎは自然数とする。２数ｘ，ｙの和、積がともに整数のとき、ｘ^n＋ｙ^n整数であることを、数学的帰納法によって証明せよ。 という問題なのですが、解説に i)n=1,n=2のときに成り立つことを示す ii)n=k,n=k-1であると仮定して、n=k+1のときにも成り立つことを示す とありました。 また、注がついており、 『x^(k+1)+y^(k+1)=(x^k+y^k)(x+y)-xy{x^(k-1)+y^(k-1)}である』とありました。 なぜ『』だからi)でn=2を、ii)でn=k-1を書かないといけないのですか？ お願いします。
- ベストアンサー
- 数学・算数
- 数学で教科書見ても分からない所があるので分かる方
数学で教科書見ても分からない所があるので分かる方 どうやって解けばいいのか教えて頂けませんか?>_< お願いします><どうしても解けません>_< 分かる所だけでいいので、教えて頂けると嬉しいです>< 次の格式を、（）に示したものでくくりなさい。 (1)3lm-41ln+6l (l) (2)ab^2-3abc-2a^2b (ab) (3)10x^2y-25xy+15xy^2 (5xy) 次の計算をしなさい。 (1)12ab[2/3a^2+1/4ab-1/6b^2] (2)3と1/2x(y-3x)+4と1/3y(x-2y) (3)1/3ab[ab+1/3b]-1/2ab[1/3ab-1/2b] お願いします><
- ベストアンサー
- 数学・算数
お礼
Tacosan様、ご教示ありがとうございます。 具体的な証明作成を頑張ります。