- ベストアンサー
【緊急】{ww: w∈{a, b}*}はRegular language?
{ww: w∈{a, b}*}はRegular languageですよね? {ww^R: w∈{a, b}*}はNon-regular languageというのは知っています。 さっき試験が終わったばっかりで気になって仕方がありません。
- oxford
- お礼率95% (146/153)
- その他（プログラミング・開発）
- 回答数2
- ありがとう数1
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
> という場合がありえますが －－－－－－－－－－＊＊ 最後のa..ab、 を忘れていました。どっちにしても結論はかわりませんが、訂正します。 あと、ついでなので１つアドバイス的なことを。 正規表現の能力の限界は、直観的には、DFAが有限の状態しか持たないということに起因します。 例えば、(^i )^i（＝同じ数の対応する括弧）が正規表現で表せないことはご存知ですよね。 これは、「(^i が入力された時点で、今までに何個の( が入力されたかを覚えておく必要があるが、それは有限の状態では不可能だから」と理解することができます。 こう理解しておくと、証明するまでもなく、{ww: w∈{a, b}*} は正規言語ではないということが予想できるかと思います。
その他の回答 (1)
- hpsk
- ベストアンサー率40% (48/119)
残念ながら（？）、{ww: w∈{a, b}*} も Non-regular です。 これは、{ww^R: w∈{a, b}*}が Non-regular であることの証明とほぼ同じように示すことが出来ます。 あまり厳密な証明ではないですが、簡単に説明すると・・・ {ww: w∈{a, b}*}を受理するDFAが存在したとすると、 このDFAは、(a^n)b(a^n)b という記号列を受理するはずです（a^nはaのn個の並び）。 DFAの状態数は有限なので、nがある一定以上大きくなると記号列長が状態数を超えます。 そのような記号列を受理するためには、必ずDFA中の同じ状態を2度通る必要があります。つまり、 Sk → ... → Sk という遷移のループがDFAに必ず存在します。 (a^n)b(a^n)bを受理した際、このループで処理した記号列は、 ａ．．．ａｂａ．．．ａｂ のうち、 －＊＊＊－－－－－－－－ このあたりか（前半のa)、 －－－－＊＊＊－－－－－ このあたりか（a...aba...a、または前後のaを含まない場合）、 －－－－－－－＊＊＊－－ このあたりか（後半のa)、 －－－－－－－－－－－＊ 最後のbだけ、 という場合がありえますが（多分表示がずれますが、だいたいわかりますよね）、 このうちのどれであったとしても、このようなループが存在すると、このDFAは{ww: w∈{a, b}*} に含まれない記号列も受理できることになってしまいます。 これは矛盾であり、{ww: w∈{a, b}*}を受理するDFAは存在せず、つまり{ww: w∈{a, b}*}は正規言語ではない、ということになります。
関連するQ&A
- $a[0]='w';$a[1]='r';を1回で
$a=array(); $a[0]='w'; $a[1]='r'; 2行目と3行目を$a=はてな('w','r'); のように書くことはできませんか？
- 締切済み
- PHP
- オートマトン L = {ww^R: w ∈ {a, b}+}の中心の見つけ方
下記のようなオートマトンがあります。 L = {ww^R: w ∈ {a, b}+} M = (Q, Σ, Γ, δ, q0, z, F) Q = (q0, q1, q2), Σ = {a, b}, Γ = {a, b, z}, F = {q2}. (1)wをスタックに載せるために: δ(q0, a, a) = {(q0, aa)} δ(q0, b, a) = {(q0, ba)} δ(q0, a, b) = {(q0, ab)} δ(q0, b, b) = {(q0, bb)} δ(q0, a, z) = {(q0, az)} δ(q0, b, z) = {(q0, bz)} (2)どこが文の中心か見つけるために(状態がq0からq1に変わる): δ(q0, λ, a) = {(q1, a)} δ(q0, λ, b) = {(q1, b)} (3)w^Rと一致させるために: δ(q1, a, a) = {(q1, λ)} δ(q1, b, b) = {(q1, λ)} (4)最後に: δ(q1, λ, z) = {(q2, z)} とあります。 問題の中にこれを元にしてL = {wcw^R: w ∈ {a, b}*}のnpdaをつくりなさい、 というのがありますが、それは(2)を δ(q0, c, a) = {(q1, a)} ←cが入力されたらそこが中心 δ(q0, c, b) = {(q1, b)} に変えて δ(q0, λ, z) = {(q2, λ)} ←何も入力されなかったら文字を受け付ける(* → +なので) を付け加えればよいですか? (多分、そうですよね?) それと、上の(2)がどうやって中心を見つけているのか分かりません。 入力中は何文字入力されるかなんて分かりませんよね。 例えばbaabbaabという文があったとすると最初の四文字でbaabで 「さては中心はbaとabの間だな!」とか勘違いとかしないんですか? 入力がλということは毎回毎回入力がある度にチェックしているということでしょうか? 混乱している私に分かりやすい説明ができる方、どうかお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- Aさん、Bさん、私がいます。
Aさん、Bさん、私がいます。 AさんはBさんのメールアドレスが知りたい。 Aさんは、Bさんと私が友達同士なのでお互いのアドレスを知っている事を知っている。 Aさんは私に「Bさんのメールアドレス知ってる？」とメールしてきた。 でも私とBさんは、Aさんの事を良く思ってないので絶対に教えたくない。 音信不通・無視 これ以外で上手いはぐらし方はありませんか？
- ベストアンサー
- その他(恋愛・人生相談)
- 緊急です ＡはＢに１５００円貸していて大きな問題に
緊急です ＡとＢがいます ＡはＢに１５００円貸しています 一か月以上たってもＢは返す気がありません ＡはＢが見ている前でＢのお金をとりました そのあと、ネットに本名と悪口をかきこまれたそうです Ｂは被害届をだすつもりで Ａは名誉毀損で訴えるつもりです どうしたらよいですか？
- ベストアンサー
- その他（マネー）
- (a+b)(a-b)=a^2+b^2
別の方の質問で表題の式は間違いかどうか尋ねるものを見かけて気になったので質問します。 実数や複素数のように可換な体で考える分には自明な場合（b=0）しかありませんが、そうでない場合、たとえばa、bを2行2列の行列と考えて、aの(i,j)成分をa(i,j)と表記するとして、数c,d,s,u(u≠0)を用いて a(1,1)=d a(1,2)=-(s^2)c/(u^2) a(2,1)=c a(2,2)=d b(1,1)=s b(1,2)=-(s^2)/u b(2,1)=u b(2,2)=-s によってaとbを定義すると、(a+b)(a-b)=a^2+b^2を満たすことがわかります。このときb^2=0でありab=baです。 一般の環でも同様のことは言えますか？つまり上記より強く、(a+b)(a-b)=a^2+b^2を満たすには、「b^2=0かつab=ba」は必要条件になるでしょうか？ 初歩的なことかと思いますが、よろしくお願いします。
- 締切済み
- 数学・算数
- μ((a,b))=∫[a..b]x^2dx (-∞<a<b<∞)は何故,全ボレル集合体B(R)の一意的測度?何故μ({0})=0なの?
こんにちは。よろしくお願い致します。 測度の定義は (Ω,B)を可測空間(BはΩ上σ集合体)とする時,fが (i) ∀b∈B,f(b)∈[0,∞],f(φ)=0. (ii) f(∪[k=1..∞]b_k)=Σ[k=1..∞]f(b_k) (B∋b_1,b_2,…は互いに素) を満たせば(Ω,B)上の測度という。 ボレル集合体の定義は 位相空間(X,T)においてσ(T):={B;T⊂B,BはX上のσ集合体}をB(X)と書き,X上のボレル集合体という。 有限加法族の定義は (i) Ω∈B, (ii) b∈B⇒b^c∈B, (iii) b,c∈B⇒b∪c∈B. の時,BをΩ上の有限加法族という。 a finite measureの定義は (i) Bが有限加法族, (ii) fは(Ω,B)上の測度, (iii) f(b_1∪b_2)=f(b_1)+f(b_2) (B∋b_1,b_2は互いに素) の時,Bを(Ω,B)上のa finite measureという。 a σfinte measureの定義は (i) fは(Ω,B)上のa finite measure, (ii) Ω=∪[i=1..∞]b_i且つf(b_i)∈R (B∋b_1,b_2,…は互いに素), の時,fを(Ω,B)上のa σfinite measureという。 です。 [Q] Define a measure μ on open intervals in R by μ((a,b))=∫[a..b]x^2dx (-∞<a<b<∞) (1) Why does this uniquely determine the measure μ on all of B(R)? (2) Show μ({0})=0. (Be specific) (3) Is μ a finite measure? σ-finite? Why? という問題です。 (1)の「何故これが一意的に全B(R)(ボレル集合体)上の測度μを決定するのか?」の意味が分かりません。 1次元ボレル集合体B(R)とはσ(T):={B∈2^R;T⊂B (BはR上のσ集合体)}(Tは開集合全体の集合)だと思います。 全てのB(R)だから K_1={(a,b)∈2^R;a,b∈R}や K_2={[a,b)∈2^R;a,b∈R}や K_3={(a,b]∈2^R;a,b∈R}や K_4={[a,b]∈2^R;a,b∈R}と置くとユークリッド空間Rの位相は T_0={φ,R}, T_1={∪[λ∈Λ]G_λ;G_λ∈K_1}, T_2={∪[λ∈Λ]G_λ;G_λ∈K_2}, T_3={∪[λ∈Λ]G_λ;G_λ∈K_3}, T_4={∪[λ∈Λ]G_λ;G_λ∈K_4}, T_5=2^R はいずれもRの位相になると思いますので少なくとも B(R)は6種類が考えられると思います。 これ以外にもB(R)はあるのでしょうか? あるのならどんな位相が考えられるのでしょうか?そして網羅しつくした事をどうやって示せばいいのでしょうか? そして全B(R)上の測度μはこのμ唯一つしかない事はどうやって示せばいいのでしょうか? とりあえず,自力でやってみました。。 このμの他にB(R)(仮に位相はT_0としてみて)上の測度μ'があったとすると B(R)=σ(T_0)は∩[B∈{B;T⊂B,BはR上のσ集合体}]B={φ,R}になると思います。 そしてμ'は測度なのだから (i) ∀b∈B,μ'(b)∈[0,∞],μ'(φ)=0. (ii) μ'(∪[k=1..∞]b_k)=Σ[k=1..∞]μ'(b_k) (B∋b_1,b_2,…は互いに素) を満たさねばなりません,,,, これからμ'がμ'(φ)=0 (∵測度の定義)は言えましたが このB(R)は今{φ,R}なので区間を元に持ちませんので μ'((a,b))=∫[a..b]x^2dx (-∞<a<b<∞)と書き表せようがないと思います。 問題文を誤釈してますでしょうか? (2)については今,R上のσ集合体Bをopen intervalsにしているので {0}=∩[n=1..∞](-1/n,1/n)∈Bと言えるから∩[n=1..∞](-1/n,1/n)はμ上で定義されていている。 それで μ({0})=μ(∩[n=1..∞](-1/n,1/n))=Σ[n=1..∞]μ((-1/n,1/n)) =Σ[n=1..∞]∫[-1/n..1/n]x^2dx=Σ[n=1..∞][x^3/3]^1/n_-1/n =Σ[n=1..∞]2/(3n^3) となってしまったのですがこれは0になりませんよね。 何が間違っているのでしょうか? (3)については まずこのμがa finite measureを吟味してみますとa finite measureの定義から まずσ集合体Bが有限加法族になっていないといけません。 しかし,ここでのσ集合体Bはopen intervalsで-∞<a<b<∞となっていますので 少なくともR∈Bを満たしませんからBは有限加法族になってません。 従って,このμはa finite measureではない。 次にa σfinite measureになっているかを吟味すると, まずa finite measureになっていなければなりませんが 既にa finite measureでない事は判明済みなのでσfinite measureでもない。。。 と結論づいたのですがこれで正しいでしょうか? すいません。ご教示ください。
- ベストアンサー
- 数学・算数
- 日本史ＡとＢ．．Ａのほうがふつう・・・？
こんばんは。今日、模試でした。 地歴公民の模試で、わたしは日本史Ｂで受けようと思ったのですが、 問題用紙が手元に回ってこなく、手を上げて試験官を呼び ことなくをえたのですが、そのときのことです。 試験官）「科目は何ですか？」 私）「日本史です」 試験官）「Ａですか？Ｂですか？」 私）「Ｂです」 手渡される。 後ろの人）「あの、日本史Ａをください」 試験官）「Ａですよね」 というやり取りがありました。 私には妙に「Ａですよね」がＡで当たり前。 みたいな言い方に聞こえました。 Ａのほうがふつうなのですか？ Ａは一般常識的なこと、Ｂは深く。 と理解しています。
- ベストアンサー
- その他（学問・教育）
お礼
さっき試験が返ってきました。 当然×でした、とほほ。 (^i )^iは今まで見たことありませんでした。 試験前に知っておけばよかったです。 ありがとうございました。