- 締切済み
オートマトンについて
次の問で、非決定性オートマトンと、決定性オートマトンを作りたいのですが、どうしても分かりません。 答えと、作成の方法を詳しく解説していただけると嬉しいです。 宜しくお願いします。 【問】 1と0で構成される文字列を2進数とみなしたときに、その数字が5の倍数なら受理するオートマトンを作成せよ。
- hisashichan
- お礼率23% (11/47)
- その他（学問・教育）
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
じゃあ「5で割った余りを求める」オートマトンを作ればいい. 例えば, 「5以上だったら 5 を引く」という処理を繰り返せば「5で割った余り」が求まる, ってのはいいよね? 普通はこんな作り方はしないけど, 「できない」わけじゃなくて「しない」だけ.
- Tacosan
- ベストアンサー率23% (3656/15482)
あなたなら, どのように「5の倍数かどうか」を判定しますか?
補足
オートマトンで考えてですか?? 5で割った余りが０になればいいんですよね。 5で割った余りは1，2，3，4，0だから 終了状態のところで余りが0になってればいいのでは…って感じですが…
関連するQ&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)はどのようになるのでしょうか？あるいはどのように考えればよいのでしょうか？ 分かる方みえましたら教えて下さい。
- 締切済み
- その他([技術者向] コンピューター)
- オートマトンと形式言語
オートマトンの問題で受理される語をどう答えていいかわかりません 状態変異図を見て判断するんですか？ 例えば下の有限オートマトンによって受理される言語L(M)を示せ という問題では答えはL(M)={ω∈{a}*|ωは3の倍数個のaからなる 語}になります。
- 締切済み
- 数学・算数
- オートマトンについて（３）
以下の問題も解けず困っています。よろしくお願いします。 以下の言語を受理するオートマトンを設計せよ。 L＝｛w|wは０と１からなる文字列で、どこかに100がある｝ 例えば10010∈Lである。 オートマトンは状態遷移図でも形式的表現でもよい。 オートマトンについても詳細を加えていただくとありがたいです。 よろしくお願いします。
- 締切済み
- 数学・算数
- 決定性有限オートマトンと正規表現
現在オートマトンの勉強をしていますが，どうしても分からない問題がありました． 決定性有限オートマトンについて，初期状態，受理状態共に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* となりました． ご教授よろしくお願いします．
- 締切済み
- 科学
- 確率を教えてください！
こんにちは 読んでくださってるかたありがとうございます 今確率をやっていますが、 答えがまったく出せません 問題 ６個の数字0,1,2,3,4,5から異なる４個の数字を選んで,４桁の数をつくるとき,次の問いに答えなさい。 3の倍数は何通りできますか。 教えてください お願いします
- 締切済み
- 数学・算数
- 非決定性オートマトンから正規表現への変換について
NFA（非決定性オートマトン）からregular expression（正規表現）への、変換方法がよく分かりません。 正規表現からNFAを作成するアルゴリズムは大丈夫なのですが、その逆が分からないのです。 検索して調べたものの・・・。 どこか分かりやすいWEBサイトなどありましたら 教えていただけないでしょうか？
- ベストアンサー
- その他([技術者向] コンピューター)
- この問題の簡単なあ解法はないでしょういか？
０～６までの数字がかかれたカードが１枚ずつあって、 このカードをつくって３ケタの倍数を作り、その中から５で割り切れる自然数を除いていくと最後に残る自然数はいくつか？ といった問題があります。 考えたのですが、わからなかったので、 解説をみたのですが、 それでもわからなくて私でもわかるような解法はないでしょうか？ 自分で考えたのは３ケタの３の倍数は ３つの数字のわが３の倍数になればいいので、 それを１つずつつくっていったのですが、 あまりに多すぎて時間がいくらあっても足りませんでした。 答えは４８個になるそうです。 何か良い方法はないものでしょうか？
- ベストアンサー
- 数学・算数
- 熊本大学 ２００１年 過去問４
袋の中に1 から5 までのいずれかの数字を書いた同じ形の札が15 枚入っていて，それらは1 の札が1 枚，2 の札が2 枚，3 の札が3 枚，4 の札が4 枚，5 の札が5 枚からなる．袋の中からこれらの札のうち3 枚 を同時にとり出すとき，札に書かれている数の和をS とする．このとき，次の問いに答えよ． (1) S が2 の倍数である確率を求めよ． (2) S が3 の倍数である確率を求めよ． 答え(1) 236 455 (2) 151 455 答えの表記が悪くて済みません （１）は４５５分の２３６ （２）は４５５分の１５１です 解説がないので答えまでたどり着けません。 よろしくおねがいします。
- 締切済み
- 数学・算数
補足
言ってることは分かります!!