締切済み オートマトンと形式言語 2015/06/04 19:32 オートマトンの問題で受理される語をどう答えていいかわかりません 状態変異図を見て判断するんですか? 例えば下の有限オートマトンによって受理される言語L(M)を示せ という問題では答えはL(M)={ω∈{a}*|ωは3の倍数個のaからなる 語}になります。 画像を拡大する みんなの回答 (1) 専門家の回答 みんなの回答 f272 ベストアンサー率46% (8469/18131) 2015/06/05 18:44 回答No.1 状態変異図を見ればわかるでしょう。 通報する ありがとう 0 広告を見て他の回答を表示する(0) カテゴリ 学問・教育数学・算数 関連するQ&A オートマトン (1)決定性有限オートマトンが与えられているとき、Mによって受理される言語L(M)が存在しないかどうかを判定するアルゴリズムを与え、その正当性について議論せよ (2)Σを有限の入力アルファベットとする。2つの決定性有限オートマトンM1=(Q1,Σ,δ1,q1,F1)とM2=(Q2,Σ,δ2,q2,F2)が入力として与えられたとき、L(M1)がL(M2)に含まれるか否かを判定するアルゴリズムは存在するか。存在するならアルゴリズムの概要を書け。存在しなければそのことを証明せよ。 という問題の解答が分かりません。 どなたか教えてください。 このオートマトンの問題 ∑={0,1}上の言語L1,L2について L1:0を含まないか、0を3の倍数個だけ含む全ての文字列からなる集合 L2:1を含まないか、1を偶数個だけ含む全ての文字列からなる集合 (a)L2を長さ9以内の正規表現で表わし、その長さも書け。 (b)L1∩L2を受理する決定性有限オートマトンの状態遷移図を示せ。 正規表現は拡張BNFで定義されています (a)は(0+(1+0*)1)*と書けそうかなと思います(間違いかもしれません)が、長さはいくつになるのでしょうか? (b)はどのようになるのでしょうか?あるいはどのように考えればよいのでしょうか? 分かる方みえましたら教えて下さい。 オートマトンについて(3) 以下の問題も解けず困っています。よろしくお願いします。 以下の言語を受理するオートマトンを設計せよ。 L={w|wは0と1からなる文字列で、どこかに100がある} 例えば10010∈Lである。 オートマトンは状態遷移図でも形式的表現でもよい。 オートマトンについても詳細を加えていただくとありがたいです。 よろしくお願いします。 オートマトンについて 次の問で、非決定性オートマトンと、決定性オートマトンを作りたいのですが、どうしても分かりません。 答えと、作成の方法を詳しく解説していただけると嬉しいです。 宜しくお願いします。 【問】 1と0で構成される文字列を2進数とみなしたときに、その数字が5の倍数なら受理するオートマトンを作成せよ。 有限オートマトン 有限オートマトンの問題で, 「任意の有限オートマトンAとBについて, T(A)=T(B)が成立するかどうかを判定できるか. ただしT(A),T(B)とは有限オートマトンA,Bが それぞれ認識する言語のことである.」 というのがあるのですが,まったく方針がたたなくて 困っています.どなたかよろしくお願いします. オートマトンについての問題 提示された言語を受理するオートマトンを作成する問題を解いていたのですが、 いくつか分からないものがありました。 ご存知の方おられましたらご教授の程よろしくお願いいたします。 (1)L = {w | 2#a(w) = #b(w)} (ただし、#x(w) は w 中の x の個数を表わす。) (2)L = {wcw | w ∈ Σ∗, c ∈ Σ} (ここで、Σ = {a, b}であり、Σ∗はΣ上の全ての語の集合) オートマトンの正則表現の式変形について オートマトンMが受理する言語L(M)を正則表現で表す問題を先日やったのですが、計算途中で式が変形できなくなってしまい、答えにたどり着くことが出来ませんでした。自力で変形したところまでも結果は、スター閉包を*で表すと、 L(M) = a*+a*ba*b(b+aa*ba*b)*aa* です。友人数人と何度も何度も確認し、ここまでは合っているということが確認できました。 答えのほうですが、L(M)=(a*+ba*bb*a)*です。 なにか公式があるのかとも思って調べてみたのですが良くわかりませんでした。 詳しい方おりましたら簡単な質問かもしれませんがよろしくお願いします。 決定性有限オートマトンと正規表現 現在オートマトンの勉強をしていますが,どうしても分からない問題がありました. 決定性有限オートマトンについて,初期状態,受理状態共にp,入力信号を0,1とする. 状態遷移表が以下の時,受理する言語を表す正規表現を求めよ. 0 1 p | p r q | p r r | q r 答え (0*11*0(11*0)*0)*0* という問題なのですが,状態消去法で自分でやってみても全然この答えになりません. ちなみに自分の解答は (0*1(1+01)*00)*0* となりました. ご教授よろしくお願いします. プッシュダウンオートマトンが! プッシュダウンオートマトンの問題がわからないんですが、基本中の基本過ぎて参考書に載っていません(><) もしよかったら軽くヒントのようなものを出していただけないでしょうか?? L={aのn+1乗bのn乗|nZ|} を受理するプッシュダウンオートマトンを書け これはn+1の1ぶん補助テープがあまってしまうのでしょうか?? なにがなんだかさっぱりです↓ 正規表現とオートマトンについての問題です。 正規表現とオートマトンについての問題です。 下記の決定性有限オートマトンMが受理する言語L(M)を正規表現で表したい。以下のカタカナ に入る記述を穴埋めしなさい。 状態iから状態jに、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 エ=?ホ=?マ=?ミ=?ム=?メ=?モ=?ヤ=? 途中までは解けたんですが?の箇所がわかりません・・・ よろしくお願いします。 オートマトン(正則表現について) カテゴリがよくわからなかったのでこちらで質問させていただきます。 今、オートマトンについて学んでいるのですが正則表現において同じ言語を 探す問題がよくわかりません。ちなみに問題は、 (0+1)*と同じ言語を表すのを探せという問題です。 これは0,1からなるすべての記号列の集合と書かれていました。 ちなみに選択肢は3つです。 (1)(1*+0*)(2)(1*+0)*(1+0)(3)(1+0*)(1*+0*)*1の3つです。 ちなみに演算の順番などはわかります。どのように同じ言語とみなすのかよくわかりません。 (0+1)*は(0*1*)*に直せるので任意個の0から始まり任意個の1が続く列が 任意個並んでいるという解釈を自分ではしています。あっているかはわかりませんが@@;) それで他の選択肢もこのように直したりして見分けるのでしょうか? 後やはり0からはじまる列と1から始まる列や、 0で終わる列と1で終わる列では表すものはちがいますよね? 始めたばかりでまだ理解しきれていませんが 回答お願いします<(_ _)> 無限状態オートマトンの説明 教科書の以下の説明が1週間ぐらい何度も試みたのですが理解できません。 無限状態オートマトンとしては入力wに関する情報として系列wそのものを 状態qwとして覚えるものと考え、状態遷移関数をw∈Σ*,a∈Σにたいして δ(qw,a)=qwaと定義する。 開始状態をqεとし、受理状態の集合として、F={qw|w∈L}と指定する。 このように指定したオートマトンにw=a1a2・・・anを入力すると、 qε→qa1→qa1a2→・・・→qa1・・・anと遷移し、w∈Lのとき、qwは受理状態 であるのでwは受理される。 宜しくお願いします。 オートマトン 教えてください 以下のオートマトンM=<Q, Σ, δ, q0, F>の状態 遷移図を描け.また入力abcbaを与えたとき の動作を⊢を用いて示せ. • Q={r, s} • Σ={a, b, c} • δ: Q✕Σ→Q • δ(r, a)={s}, δ(r, b)={r}, δ(r, c)={r} • δ(s, a)={r}, δ(s, b)={s}, δ(s, c)={s} 有限オートマトンの限界 文系の大学生ですが理系の学問も少しかじっていますが、全くわからないのです。 とくに教科書の有限オートマトンにかんするこの記述がよくわかりません 「有限状態機械で定義できる言語はかなり限定されている。 ab,aabb,aaabbb,・・・ のように文字aがn個続いた後、n個の文字bが現れるような文字列からなる 言語を定義することが出来ません」 え・・・なんでできないんですか・・・?そのあと文脈自由文法なら正規文法で書けなかったab,aabb,aaabbbのパターンの定義も書ける、と書いてあるのですが、それもよくわかりません。こんなオバカですけど、どうしても理解したいので、説明よろしくおねがいします!m(._.)mちなみにとても急いでいます!よろしくおねがいします!! ある言語クラス判定問題(正規言語?文脈自由言語?) 形式言語に関する以下の問題に悩んでおります。 問題: 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)ではない。理由はかくかくしかじか)でもありがたいですので、どうぞよろしくお願いいたします。 言語理論の文脈自由言語について 「オートマトン 言語理論 計算論I」という本(教科書)を読んでいます。 この本には演習問題がついているのですが、本を読んだだけでは解法が分らない上、 答えがついてないため、解けない問題が多く困っています。 (連休明けに試験があり、その範囲なんです。) ある言語が文脈自由型ででないことを証明したいのですが、 反復補題(パンピングレンマ)を用いて背理法によるのだろうと思うのですが、 どのように仮定するかの方針が立たないのです。 具体的には次のような問題に対し、「…」のような仮定をしてみました。 a){a^i b^j c^k | i<j<k} 「z=a^n b^(n+l) c^(n+m) (但し、m>l>0)」 しかし、下記のように背理法による矛盾が示せなかったのです。 どこで間違ったのかは分らないので、間違った個所を指摘していただきたいのです。 よろしくお願いします。 「言語を文脈自由言語と仮定する。 nをパンピングレンマの性質を持つ整数とし、 z=a^n b^(n+l) c^(n+m) (但し、m>l>0)とすると、 z∈L かつ |z|≧n が成立する。 したがって、パンピングレンマから z=u v w x y (ux≠ε、|vwx|≦n) と表され、かつ u v^i w x^i y ∈ L が成立する。 |vwy|≦n なので、vxがaとcの両方を含むことはない。 vxのパターンにより次の2つの場合を考える (i)vxが一種類の文字だけからなる場合 … (ii)vxが2種類の文字からなる場合」 ここまで書いたところで、 v=b、x=c とすると、例えば、 u=a、w=bb、y=ccc の場合を考えると、矛盾が導けないことに気付きました。 センターの整数問題 こんばんは。センターの模試で質問があります。こんな問題です。 M、Nは自然数として、 「Mが2の倍数でかつ3M+2Nが6の倍数でない」ならば「N^2+αは3の倍数」が真であるような2桁の自然数αは□□個ある。 解答は、2Nが6の倍数でないからNは3の倍数でないということに注目してN=3L+-1(L整数)だからN^2+α=3(3L^2+-2L)+1+α として求めてます。確かにこれで解けますが、なぜ突然Nの倍数性に注目しようとしたのでしょうか? すみませんが教えてください! 正規言語に対する繰り返し定理による証明 正規言語に対する繰り返し定理による証明 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の個数)のとき で場合分けをすればいいとは思うのですが・・・ どう矛盾を導きだせばいいのかが分かりません。 ご教授願います。 正規表現とDFAについて 今回も正規表現のことについてなんですが@@; いきなりなのですが正規表現 1*((00)*+(11)*)と同じ言語を受理する 状態数最小の決定性有限オートマトンを構成せよという問題なのですが (1)まずこの正規表現が表しているのは初めに0個以上の1の列が続き その後に偶数個の0または1の列が続く、偶数個の0または1の列の後には 1もしくは0の列はこない。というような解釈でいいのでしょうか? (2)問題の解き方なのですが自分としてはまず非決定性有限オートマトン(NFA) を作りそれを決定性有限オートマトンに変換して求めると思っているのですが あっているのでしょうか? (3) (2)の解き方をするとまず状態遷移図を書きたいのですがなかなかうまくいきません。やはり慣れなどがあるのでしょうか?正規表現を見ただけですぐに状態遷移図が考えつかなく@@; それで自分なりにやってみたのですが状態遷移図は見にくいと思うので 状態遷移表みたいな感じで書きます。 初期状態はq0で最終状態はq3,q5にしています。 ※NFAからDFAに変換するための状態遷移表ではないです。 状態の集合 | 0 | 1 | ------------------------------------------------ q0 空集合 [q0,q1] q1 q2 q4 q2 q3 空集合 q3 q2 空集合 q4 空集合 q5 q5 空集合 q4 のような感じになったのですがなにか誤っているでしょうか? なかなかイメージがつかめなくて; なんか表示がヘンになるかもです。 長文、駄文ですみませんがよろしくお願いします<(__)> オートマトンの反復補題。 {xx^r | x∈T^*} (x^rはxと文字列が逆さま。つまりxx^rは回文) が正規言語でないことを証明せよという問題で、他の問題を参考にして自分ではこう考えました。 Lが正規言語と仮定し、状態数nについて、 z = a^nb^nb^na^n を考える。 |z|>n であり、 z = uvw ,|uv|≦n ,|v|≧1 となるu,v,wが存在して 任意のiについて、 uv^iw ∈ L 今i=0とおく。v=a^k (k≧1)であるから、 uw中のaの数は n + n-k uw中のbの数は n + n よってa^nb^nb^na^nはaとbの数が等しくないといけないから uw ∈ L に矛盾。 よってLは正規言語ではない。 これはあってますか?回答がないため、確認する手段がなく困っています。 もし違っていればその箇所をご指摘ください。 注目のQ&A 「前置詞」が入った曲といえば? 新幹線で駅弁食べますか? ポテチを毎日3袋ずつ食べています。 優しいモラハラの見抜き方ってあるのか モテる女性の特徴は? 口蓋裂と結婚 らくになりたい 喪女の恋愛、結婚 炭酸水の使い道は キリスト教やユダヤ教は、人殺しは地獄行きですか? カテゴリ 学問・教育 人文・社会科学 語学 自然科学 数学・算数 応用科学(農工医) 学校 受験・進学 留学 その他(学問・教育) カテゴリ一覧を見る あなたにピッタリな商品が見つかる! OKWAVE セレクト コスメ化粧品 化粧水・クレンジングなど 健康食品・サプリ コンブチャなど バス用品 入浴剤・アミノ酸シャンプーなど スマホアプリ マッチングアプリなど ヘアケア 白髪染めヘアカラーなど