• 締切済み

オートマトン

教えてください 以下の状態遷移図で表されるオートマトンM を形式的な5字組で示したらどうなりますか

画像を拡大する

みんなの回答

  • f272
  • ベストアンサー率46% (8047/17199)
回答No.1

({q0,q1,q2,q3},{a,b,ε},δ,q0,{q3})だよね。 ただしδは以下のとおり。 ______a______b_______ε →q0__{ｑ2}___φ______{ｑ1} q1____φ______φ______{ｑ2} q2____φ_____{q1,q3}__φ *q3___φ______φ______φ

全文を見る
すると、全ての回答が全文表示されます。
  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • オートマトンについて（３）

    以下の問題も解けず困っています。よろしくお願いします。 以下の言語を受理するオートマトンを設計せよ。 L＝｛w|wは０と１からなる文字列で、どこかに100がある｝ 例えば10010∈Lである。 オートマトンは状態遷移図でも形式的表現でもよい。 オートマトンについても詳細を加えていただくとありがたいです。 よろしくお願いします。

  • オートマトン

    教えてください 以下のオートマトン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}

  • オートマトンと形式言語

    オートマトンの問題で受理される語をどう答えていいかわかりません 状態変異図を見て判断するんですか？ 例えば下の有限オートマトンによって受理される言語L(M)を示せ という問題では答えはL(M)={ω∈{a}*|ωは3の倍数個のaからなる 語}になります。

  • このオートマトンの問題

    ∑={0,1}上の言語L1,L2について L1：0を含まないか、0を3の倍数個だけ含む全ての文字列からなる集合 L2：1を含まないか、1を偶数個だけ含む全ての文字列からなる集合 （a）L2を長さ9以内の正規表現で表わし、その長さも書け。 (b)L1∩L2を受理する決定性有限オートマトンの状態遷移図を示せ。 正規表現は拡張BNFで定義されています (a)は(0+(1+0*)1)*と書けそうかなと思います（間違いかもしれません）が、長さはいくつになるのでしょうか？ (b)はどのようになるのでしょうか？あるいはどのように考えればよいのでしょうか？ 分かる方みえましたら教えて下さい。

  • 無限状態オートマトンの説明

    教科書の以下の説明が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は受理される。 宜しくお願いします。

  • オートマトン

    (1)決定性有限オートマトンが与えられているとき、Mによって受理される言語L(M)が存在しないかどうかを判定するアルゴリズムを与え、その正当性について議論せよ (2)Σを有限の入力アルファベットとする。２つの決定性有限オートマトンM1=(Q1,Σ,δ1,q1,F1)とM2=(Q2,Σ,δ2,q2,F2)が入力として与えられたとき、L(M1)がL(M2)に含まれるか否かを判定するアルゴリズムは存在するか。存在するならアルゴリズムの概要を書け。存在しなければそのことを証明せよ。 という問題の解答が分かりません。 どなたか教えてください。

  • オートマトンが分かりません！！

    現在情報関係の大学に通っていて、もうすぐ『オートマトンと言語理論 』という科目のテストがあります。教科書は森北出版で著者が富田悦次・横森　貴の『オートマトン・言語理論』を使っています。テスト範囲が有限オートマトンと正則表現／言語と形式文法のところなんですが正直まったく内容が理解できないです。そこの範囲を例題などを中心に初心者でも分かりやすく書いてあるオススメの参考書を知っていたら教えてください！

  • 決定性有限オートマトンと正規表現

    現在オートマトンの勉強をしていますが，どうしても分からない問題がありました． 決定性有限オートマトンについて，初期状態，受理状態共に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* となりました． ご教授よろしくお願いします．

  • 状態遷移図とチューリングマシンとは

    アルゴリズムについて学んでいた際、 「状態遷移図」と「チューリングマシン」という言葉が出てきました。 この二つはどういう関係と意味を持っているのでしょうか？ 調べてみたのですがオートマトンやら難しい計算式ばかり出てきてあまり理解できませんでした。 計算式を見て理解できないならそれまでなのかもしれませんが、 何か比較的簡単な説明を頂けないでしょうか？ お願いします。

  • 正規表現とオートマトンについての問題です。

    正規表現とオートマトンについての問題です。 下記の決定性有限オートマトン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 エ=?ホ=?マ=?ミ=?ム=?メ=?モ=?ヤ=? 途中までは解けたんですが?の箇所がわかりません・・・ よろしくお願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する