ベストアンサー

L={a^m (- {a}* | mは素数｝　この言語は正規言語になら

2010/08/11 00:23

L={a^m (- {a}* | mは素数｝　この言語は正規言語にならないことを示せ　　　　　　　　　　　　　　　　　　　どうやって証明しますか

chujunshi
お礼率24% (9/37)

その他([技術者向] コンピューター)
回答数1
ありがとう数2

みんなの回答 （1）
専門家の回答

質問者が選んだベストアンサー

ベストアンサー

Tacosan
ベストアンサー率23% (3656/15482)

2010/08/11 03:15 回答No.1

どんな言語なのかさっぱりわからんが普通は pumping lemma

質問者

お礼 2010/08/11 13:04

a^m　　の言語です。ご回答　ありがとうございます

関連する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と素因数分解できる以上２題の証明がどうしてもわかりません。わかる方、教えてください。
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は、１０進数に直されています。（１、０だけだと、勝手に２進数扱いされてしまうのか、とも思うけれど）。１０進数と、２進数の使い分けかたなど、何か分かりましたら、お願いします。
正規部分群

ＳはＭの、ＭはＬのそれぞれ正規部分群であるが、ＳがＬの正規部分群でないよう三つの群Ｓ，Ｍ，Ｌの例にはどのようなものがあるのでしょうか？なかなか、条件を満たすような、三つの群が見つかりません。解答お願いいたします。
指数にまつわる同値関係　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言語はあまり得意ではないので困っています。お分かりになる方、ご教授お願い致します。
プールの水1/2l＝500l?又、2mのテープ1/4は何mか？→1/2

プールの水1/2l＝500l?又、2mのテープ1/4は何mか？→1/2ｍ？（分数で答える場合）　質問1:例えば、プールの水の量が１万リットルだとします。この時、「プールの水1/2lは？」と問われたら、５００lとなりますか？　　また「プールの水の1/2の量は？」と問われたら、5000lとなりますか？　質問2:2mのテープの1/4は、何m?と問われたら、分数で答える場合、1/2mとなりますか？そうである場合、その理由はこの問いから1mを１として考えるから、2mの1/4＝0.5であるから1/2m（１mの1/2は0.5）となるからでしょうか？

L={a^m (- {a}* | mは素数｝　この言語は正規言語になら

質問者が選んだベストアンサー

お礼 2010/08/11 13:04

関連するQ&A

正規言語に対する繰り返し定理による証明

ある言語クラス判定問題(正規言語?文脈自由言語?)

正規数と素因数分解に関する証明問題

v,a,l,mで単語など

L=9(A^2)-2(n+1)*Aについて

L1 ⊆ L2であるか確認できるアルゴリズム

c言語　正規表現

R=ρL/AでΔRを考えた時、ΔR/R=Δρ/ρ+ΔL/L-ΔA/Aで

完全数について

MとL

式をC言語で立てれません

C言語で、２進数を扱うには。

正規部分群

指数にまつわる同値関係　a=b⇔a^m=b^m

ＭかＬかどちらでしょうか？

言語周波数について

正規表現のm{}

言語理論の文脈自由言語について

式をC言語で立てれません

プールの水1/2l＝500l?又、2mのテープ1/4は何mか？→1/2

注目のQ&A

カテゴリ
一覧

専門家に質問してみよう
専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

L={a^m (- {a}* | mは素数｝ この言語は正規言語になら

質問者が選んだベストアンサー

お礼 2010/08/11 13:04

関連するQ&A

正規言語に対する繰り返し定理による証明

ある言語クラス判定問題(正規言語?文脈自由言語?)

正規数と素因数分解に関する証明問題

v,a,l,mで単語など

L=9*(A^2)-2*(n+1)*Aについて

L1 ⊆ L2であるか確認できるアルゴリズム

c言語 正規表現

R=ρL/AでΔRを考えた時、ΔR/R=Δρ/ρ+ΔL/L-ΔA/Aで

完全数について

MとL

式をC言語で立てれません

C言語で、２進数を扱うには。

正規部分群

指数にまつわる同値関係 a=b⇔a^m=b^m

ＭかＬかどちらでしょうか？

言語周波数について

正規表現のm{}

言語理論の文脈自由言語について

式をC言語で立てれません

プールの水1/2l＝500l?又、2mのテープ1/4は何mか？→1/2

注目のQ&A

カテゴリ 一覧

専門家に質問してみよう 専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

L={a^m (- {a}* | mは素数｝　この言語は正規言語になら

L=9(A^2)-2(n+1)*Aについて

c言語　正規表現

指数にまつわる同値関係　a=b⇔a^m=b^m

カテゴリ
一覧

専門家に質問してみよう
専門家登録