ベストアンサー L={a^m (- {a}* | mは素数｝ この言語は正規言語になら 2010/08/11 00:23 L={a^m (- {a}* | mは素数｝ この言語は正規言語にならないことを示せ どうやって証明しますか みんなの回答 （1） 専門家の回答 質問者が選んだベストアンサー ベストアンサー Tacosan ベストアンサー率23% (3656/15482) 2010/08/11 03:15 回答No.1 どんな言語なのかさっぱりわからんが普通は pumping lemma 質問者 お礼 2010/08/11 13:04 a^m の言語です。ご回答 ありがとうございます 広告を見て全文表示する ログインすると、全ての回答が全文表示されます。 通報する ありがとう 0 カテゴリ [技術者向] コンピューターその他([技術者向] コンピューター) 関連する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の個数)のとき で場合分けをすればいいとは思うのですが・・・ どう矛盾を導きだせばいいのかが分かりません。 ご教授願います。 ある言語クラス判定問題(正規言語?文脈自由言語?) 形式言語に関する以下の問題に悩んでおります。 問題: 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)ではない。理由はかくかくしかじか)でもありがたいですので、どうぞよろしくお願いいたします。 正規数と素因数分解に関する証明問題 正規数と素因数分解に関する証明問題です。 xが正規数（1/xが60進有限小数） ⇔x=2^a3^b5^cと素因数分解できる xが正規数（1/xが12進有限小数） ⇔x=2^a3^bと素因数分解できる 以上２題の証明がどうしてもわかりません。 わかる方、教えてください。 ネットワークエンジニアとは？技術職の未来を考える OKWAVE コラム v,a,l,mで単語など v,a,l,mで言葉や単語を作ってください L=9*(A^2)-2*(n+1)*Aについて 任意の自然数ｎに対して、 Ｌ＝９＊（Ａ＾２）－２＊（ｎ＋１）＊Ａ、とするとき Ａを自然数の中から自由に選べるとき、Ｌを平方の数に必ずすることができるか という質問をしたいです。 L1 ⊆ L2であるか確認できるアルゴリズム なんとなく分かるんですがどうやって証明すればいいのか分かりません。 Show that there exists an algorithm for determining if L1 ⊆ L2, for any regular languages L1 and L2. すべての正規言語L1とL2に対して L1 ⊆ L2であるか確認できるアルゴリズムが存在することを証明せよ。 L1 ⊆ L2っていうのは大きな集合L2の中に小さな集合L1がすっぽり入った図でいいんですよね? 自分なりに考えると L2 - L1の結果が空集合ΦならL2とL1は重なっていない、 L2 - L1の結果でL2が少し欠けた(でもその欠け < L1)場合はL2とL1は部分的に重なっている。 L2 - L1の結果でL2の欠けた部分=L1ならL1 ⊆ L2 …っていうのじゃダメですよね? もっとスマートに証明する方法を教えて下さい。 c言語 正規表現 c言語でCSVファイルに書かれている数字を集計するシステムを作っています。 Excelでは「*」が正規表現ですが、c言語では正規表現はありますか？ よろしくお願いします。 R=ρL/AでΔRを考えた時、ΔR/R=Δρ/ρ+ΔL/L-ΔA/Aで R=ρL/AでΔRを考えた時、ΔR/R=Δρ/ρ+ΔL/L-ΔA/Aであることを証明したいのですが、どういう手順、方法で考えていいかわかりません。微分を使うのでしょうか・・・？＞＜ 何かヒントを下さいm(_ _)m 完全数について mが偶数の完全数であると仮定して諸条件は mの部分要素がm = (2^a)*b で a ∈ Z+, bは奇数、です。 このとき 1) σ(m) = (2^(a+1)) * bである事の証明 2) σ(m) = σ(b) * σ(2^(a+1)) -1)の証明 3) 2^(a+1)はσ(b)を割り切れる事の証明 がわかりません。(2)は乗法的関数である事を示せばいいのでしょうが、過程が思いつきません。(1)と(3)はさっぱりわかりません。どなたかご教授おねがいします。 MとL ネットでパーカー買おうかと思ってるんですけどサイズ迷ってます。 身長173でごく普通の体型なんですけど ・身幅 M/50 L/53 ・身丈 M/64 L/67 ・裄丈 M/83 L/87,5 どっちでしょうか？ 基本的には店では試着してMな事が多いですけどたまにLの時あります。 数字を気にした事がなくネットで服買った事ないので困ってます。 式をC言語で立てれません 式をC言語で立てれません 式をC 言語で立てれません こんにちは。私は今実験で円板振動子の中心軸上の音圧分布を求めています。 そこで写真のような図をプロットするために与えられた式をC言語で書いています。 式の詳細は P/2ρcV ＝ |sinπ(√(r/λ)^2 + (a/λ)^2)(√はここまで)-(r/λ))| です。 しかしうまくプロットできません。 プログラムは ------------------------------------- #include <stdio.h> #include <math.h> #define F 120 //周波数(Hz) #define C 1500 //音速(m/s) #define A 0.2 // 半径(m) int main() { double x, m, s, p, o, w, l; int i; for (i=0; i<100; i++) { x= (double)i; //観測点までの距離を表しました。距離が変化することで音圧が変わるためです。 l = C/F; //λをlとして音速÷周波数で定義できます。 m = x/l; //x軸です。 o = m*m + (A/l)*(A/l); //式のsinの中身です。 s = sin(M_PI*(sqrt (o) - m)); //sin全体を定義します。 w = fabs(s); //sin全体を絶対値に置き換えます。 p = w; //新しい変数に入れます。 printf("%9.9f %9.9f＼n", m, p); } return 0; } ------------------------------ といった感じです。先生からはx軸のプログラムだけいじれば勝手に y軸も出てくるとヒントを頂いているのでx軸についてのプログラムを 書いています。コンパイルはできても写真のようにいきません。 半径やλや周波数はa/λ=2.5と書いてあったので値は推測です。 C言語はあまり得意ではないので困っています。 お分かりになる方、ご教授お願い致します。 ※式が間違っていたので新しく質問します。 C言語で、２進数を扱うには。 C言語で、２進数を扱いたいのですが、 よく分かりません。 ためしに、 int a=2,int b=1 で、 int c=a | b printf("answer=%d"),c) とすると、３となります。 a & bだと、０です。 この場合、a,bは２進数変換されて、 計算され、表示は、１０進数に 直されて、表示されているようです。 一方、 a=10,b=2とすると、 a | b=10 a & b=2です。 この場合、１０は２進数に直されず （そのまま２進数扱い）、 ２は２進数に直され、 表示は、a | bはそのまま２進数扱い、 a & bは、１０進数に直されています。 （１、０だけだと、勝手に２進数扱い されてしまうのか、とも思うけれど）。 １０進数と、２進数の使い分けかたなど、 何か分かりましたら、お願いします。 AIは使う人の年齢や市場にも影響する？人工知能の可能性 OKWAVE コラム 正規部分群 ＳはＭの、ＭはＬのそれぞれ正規部分群であるが、ＳがＬの正規部分群でないよう三つの群Ｓ，Ｍ，Ｌの例にはどのようなものがあるのでしょうか？ なかなか、条件を満たすような、三つの群が見つかりません。 解答お願いいたします。 指数にまつわる同値関係 a=b⇔a^m=b^m 大学入試範囲です 指数にまつわる同値関係なのですが 質問1 aが実数 bが実数 mが奇数 のとき a=b⇔a^m=b^m これはどうやら真なようなのですが （問題集でこの事実を使用していました） 自分ではうまく証明できませんでした 証明を教えてください 質問2 aが実数 bが実数 mが偶数 のとき a=b⇔a^m=b^m aが実数 bが実数 mが偶数 のとき a=bまたはa=-b⇔a^m=b^m を考えてみたのですが これも真か偽かうまく証明できませんでした 真か偽か証明を添えて教えてください ＭかＬかどちらでしょうか？ 身長164、体重48の女です。服のサイズがＭかＬかハッキリわからないのですが、どちらでしょうか？品物によって大きめとか小さめあると思いますが、Ｌだと袖が長い気がしますが、Ｍだとピッシリな気もします 言語周波数について 世界中にたくさん言語がありますが、もっとも周波数の高い言語ってどれなんでしょうか？周波数の言語を耳に慣れることが言語習得のポイントになると聞いたことがありますが、本当でしょうか。教えてください。 正規表現のm{} 正規表現の記述で、m{}と書くサンプルを目にしたのですが、このmと中括弧は何を意味するのでしょうか？ 以下、Hタグにマッチするかをテストする正規表現のサンプルです。 $_ = "<H3>ヘッダ３</H3>"; if ( m{<(H\d)>(.+)</\1>} ) { print "found!!"; } 言語理論の文脈自由言語について 「オートマトン 言語理論 計算論Ｉ」という本（教科書）を読んでいます。 この本には演習問題がついているのですが、本を読んだだけでは解法が分らない上、 答えがついてないため、解けない問題が多く困っています。 （連休明けに試験があり、その範囲なんです。） ある言語が文脈自由型ででないことを証明したいのですが、 反復補題（パンピングレンマ）を用いて背理法によるのだろうと思うのですが、 どのように仮定するかの方針が立たないのです。 具体的には次のような問題に対し、「…」のような仮定をしてみました。 ａ）｛ａ＾ｉ ｂ＾ｊ ｃ＾ｋ ｜ ｉ＜ｊ＜ｋ｝ 「ｚ＝ａ＾ｎ ｂ＾（ｎ＋ｌ） ｃ＾（ｎ＋ｍ） （但し、ｍ＞ｌ＞０）」 しかし、下記のように背理法による矛盾が示せなかったのです。 どこで間違ったのかは分らないので、間違った個所を指摘していただきたいのです。 よろしくお願いします。 「言語を文脈自由言語と仮定する。 ｎをパンピングレンマの性質を持つ整数とし、 ｚ＝ａ＾ｎ ｂ＾（ｎ＋ｌ） ｃ＾（ｎ＋ｍ） （但し、ｍ＞ｌ＞０）とすると、 ｚ∈Ｌ かつ ｜ｚ｜≧ｎ が成立する。 したがって、パンピングレンマから ｚ＝ｕ ｖ ｗ ｘ ｙ （ｕｘ≠ε、｜ｖｗｘ｜≦ｎ） と表され、かつ ｕ ｖ＾ｉ ｗ ｘ＾ｉ ｙ ∈ Ｌ が成立する。 ｜ｖｗｙ｜≦ｎ なので、ｖｘがａとｃの両方を含むことはない。 ｖｘのパターンにより次の２つの場合を考える （ｉ）ｖｘが一種類の文字だけからなる場合 … （ｉｉ）ｖｘが２種類の文字からなる場合」 ここまで書いたところで、 ｖ＝ｂ、ｘ＝ｃ とすると、例えば、 ｕ＝ａ、ｗ＝ｂｂ、ｙ＝ｃｃｃ の場合を考えると、矛盾が導けないことに気付きました。 式をC言語で立てれません 式をC言語で立てれません こんにちは。私は今実験で円板振動子の中心軸上の音圧分布を求めています。 そこで写真のような図をプロットするために与えられた式をC言語で書いています。 式の詳細は P/2ρcV ＝ |sinπ(√(r/λ)^2 + (a/λ)^2)(√はここまで)-(r/λ)^2)| です。 しかしうまくプロットできません。 プログラムは ------------------------------------- #include <stdio.h> #include <math.h> #define F 120 //周波数(Hz) #define C 1500 //音速(m/s) #define A 0.2 // 半径(m) int main() { double x, m, s, p, o, w, l; int i; for (i=0; i<100; i++) { x= (double)i; //観測点までの距離を表しました。距離が変化することで音圧が変わるためです。 l = C/F; //λをlとして音速÷周波数で定義できます。 m = x/l; //x軸です。 o = m*m + (A/l)*(A/l); //式のsinの中身です。 s = sin(M_PI*(sqrt (o) - m)); //sin全体を定義します。 w = fabs(s); //sin全体を絶対値に置き換えます。 p = w; //新しい変数に入れます。 printf("%9.9f %9.9f＼n", m, p); } return 0; } ------------------------------ といった感じです。先生からはx軸のプログラムだけいじれば勝手に y軸も出てくるとヒントを頂いているのでx軸についてのプログラムを 書いています。コンパイルはできても写真のようにいきません。 半径やλや周波数はa/λ=2.5と書いてあったので値は推測です。 C言語はあまり得意ではないので困っています。 お分かりになる方、ご教授お願い致します。 1m^3はℓに直せるか？ １立方メートルはリットルに直せますか？ やり方教えてください 注目のQ&A 「You」や「I」が入った曲といえば？ Part2 結婚について考えていない大学生の彼氏について 関東の方に聞きたいです 大阪万博について 駅の清涼飲料水自販機 不倫の慰謝料の請求について 新型コロナウイルスがもたらした功績について教えて 旧姓を使う理由。 回復メディアの保存方法 好きな人を諦める方法 小諸市（長野県）在住でスキーやスノボをする方の用具 カテゴリ [技術者向] コンピューター OS（技術者向け） データベース プログラミング・開発 業務ソフトウェア ITシステム運用・管理 その他([技術者向] コンピューター) カテゴリ一覧を見る OKWAVE コラム 突然のトラブル？プリンター・メール・LINE編 携帯料金を賢く見直す！格安SIMと端末選びのポイントは？ 友達って必要？友情って何だろう 大震災時の現実とは？私たちができる備え 「結婚相談所は恥ずかしい」は時代遅れ！負け組の誤解と出会いの掴み方 あなたにピッタリな商品が見つかる！ OKWAVE セレクト コスメ化粧品 化粧水・クレンジングなど 健康食品・サプリ コンブチャなど バス用品 入浴剤・アミノ酸シャンプーなど スマホアプリ マッチングアプリなど ヘアケア 白髪染めヘアカラーなど インターネット回線 プロバイダ、光回線など
お礼
a^m の言語です。ご回答 ありがとうございます