(1)決定性有限オートマトンが与えられているとき、Mによって受理される言語L(M)が存在しないかどうかを判定するアルゴリズムを与え、その正当性について議論せよ
(2)Σを有限の入力アルファベットとする。2つの決定性有限オートマトンM1=(Q1,Σ,δ1,q1,F1)とM2=(Q2,Σ,δ2,q2,F2)が入力として与えられたとき、L(M1)がL(M2)に含まれるか否かを判定するアルゴリズムは存在するか。存在するならアルゴリズムの概要を書け。存在しなければそのことを証明せよ。
という問題の解答が分かりません。
どなたか教えてください。
No.5ベストアンサー
- 回答日時:
ま、ヒント出しますか。
●問(1)について、
> オートマトンに初期状態と最終状態が存在するかどうか
まず、初期状態が存在するかって、q0って何でしたっけね。最終状態については、単にF≠Øを言っただけじゃ駄目です。
ところで、そのアイデアとは似ていない、もっと(アルゴリズムとしての能率が悪くても)単純明快なアプローチもあります。ポイントはアルファベットが有限集合だということ。
●問(2)に答えるには
(a) 任意の有限オートマトンMが受理する言語L(M)は正規言語である。
(b) 任意の正規言語Xに対してL(M)=Xとなる有限オートマトンMを構成するアルゴリズムがある。
(c) 任意の正規言語X, Yについて、X∩Y, X∪Y, X^c(Xの補集合)はどれも正規言語である。
(d) 有限オートマトンMについて、L(M)=Øであるかどうかを判定するアルゴリズムがある。(=問(1))
ということ(定理)を組み合わせれば足りる。おそらく、それぞれをゼロから証明しろというのではないからこそ「概要を書け」と問われているんでしょう。(a),(b),(c)について何か教わったんじゃないかと思いますが。
No.4
- 回答日時:
ANo.2へのコメントについてです。
> 判断すればいいのでしょうか。
「いいのでしょうか」と仰るということは、どうも「正当性」の意味もお分りでない?
何かアルゴリズムAを考えたのなら、「AがどんなMについても正しい結果を与える」ということの証明を試みる。もし証明できたら、それが「Aの正当性を示した」ということです。一方、Aが正しい結果を与えないようなMの存在がもし証明できれば、「AはL(M)=Øとなっているかどうかを判定するアルゴリズムではない」ということが分かり、つまりAは落第。
だから、「いいのでしょうか」と尋ねて「いいです」とか「だめです」という答を貰ったって、レポートにはならんのです。
それはさておき、まずはQ, Σ, δ, q, F, L(M)って一体何の事なのか、補足なさって下さいな。もちろん、名称を訊いているんじゃありませんよ。「どんなMについても」ということを考えるためには、何がMで何はMでないのか、つまり「決定性有限オートマトンM」というものがどう定義されているのか、明確に把握しないと話が始まらないんです。
No.3
- 回答日時:
「L(M)=Ø」は「Mによって受理される言語がない」ということではありません. 前者は「M によって受理される言語が『空集合』である」という意味です. あくまで「『空集合』として存在する」であって「存在しない」ではありません.
で「(ある語が) Mによって受理される」の意味は分かりますか?
No.2
- 回答日時:
ANo.1へのコメントについてです。
> Mによって受理される言語をL(M)と書く。
「Mによって受理される」とはどういう意味で、「言語」とは何の事か、お分かりならば(1)が出来ないはずはないと思うんですが…
どこで分かんなくなったのか、説明して下さいな。
この回答への補足
もとの問題文は、「L(M)=Øとなっているかどうかを判定するアルゴリズムを与え、その正当性について議論せよ」というものだったのですが、これはMによって受理される言語がないということと解釈してそう書きました。
どこで分からなくなったというより、何をすればいいのか分からない感じです。
受理する言語がないかどうかは、オートマトンに初期状態と最終状態が存在するかどうかを判断すればいいのでしょうか。
これがきかれていることに対する答えなのかがよくわかりません。
No.1
- 回答日時:
「(1)が分からんというのは、そもそも『有限オートマトン』や『言語』が何のことなのかを知らないということではないか?」と言われたってしょうがないような質問ですよ?
これじゃ、説明しようにも用語がどれだけ質問者氏に通じるのか分かりませんので、まずは
> 決定性有限オートマトンM1=(Q1,Σ,δ1,q1,F1)
のQ1,Σ,δ1,q1,F1がそれぞれ何のことで、他の要素とどう関係するのか、そして、「受理される言語」L(M1)が何のことなのかを、補足に書いてくださいな。
この回答への補足
すみませんでした。
決定性有限オートマトンをM=(Q,Σ,δ,q0,F)と書く。
ここで、Qは状態の有限集合、Σは有限の入力アルファベット、δ:Q×Σ→Qは状態推移関数、q0は初期状態、Fは受理状態の集合とする。
Mによって受理される言語をL(M)と書く。
と問題の最初に書くべきでした。
よろしくお願いします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(形式科学) 非決定性有限オートマトンの問題について 1 2022/07/21 21:10
- 法学 既判力 時的限界について 1 2023/03/15 11:46
- 計算機科学 アルゴリズムについて 1 2023/01/01 19:43
- 数学 0でも無限でもない。 4 2023/04/22 19:12
- 哲学 物語における「魔法」は「実現可能性」というくびきがなく、作者がそれ故に恣意的に設定を決めることができ 2 2022/08/20 17:04
- 物理学 ABC予想によって、宇宙が現実に存在している事が証明されましたね? 1 2022/05/13 09:31
- 数学 これが人類最初のABC予想の応用ですか? 3 2022/04/27 05:41
- 政治 ABC予想で自衛隊を合憲にする事ができますよね? 3 2022/04/23 05:46
- 数学 『数は実在するのか』 6 2023/06/04 15:15
- 物理学 物理 慣性系の存在 5 2022/09/01 11:19
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
3,4,7,8を使って10を作る
-
証明終了の記号。
-
数学の「証明」のときなどの接...
-
「証明証」と「証明書」はどう...
-
婿養子に入ったのに出て行けと...
-
素数の積に1を加算すると素数で...
-
通学証明書の契印とは
-
夫が亡くなった後の義理家族と...
-
成人した後両親が離婚し別の人...
-
婿養子です、妻と離婚して妻の...
-
アキレスと亀がなぜ不思議でな...
-
2のn乗根で、 nを無限大に持っ...
-
大学の二次試験で・・・
-
還元不能の3次方程式
-
高校数学です。 (−a)(−b)=ab を...
-
数学の証明問題で、「証明終了」...
-
ε-N論法を用いた、lim(1/an)=0...
-
つながった2つのリングを外す
-
再婚、奨学金
-
再婚を考えてますが、養子縁組...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
証明終了の記号。
-
数学の「証明」のときなどの接...
-
数学の証明問題で、「証明終了」...
-
3,4,7,8を使って10を作る
-
「証明証」と「証明書」はどう...
-
夫が亡くなった後の義理家族と...
-
(4^n)-1が3の倍数であることの...
-
松坂和夫著「集合・位相入門」...
-
じゃらんで旅行予約をしたので...
-
素数の性質
-
素数の積に1を加算すると素数で...
-
図形の証明は、日常で役立ちま...
-
なぜ独身だと養子が持てないの...
-
大学の給付型奨学金について 現...
-
再婚、奨学金
-
正解が一つとは限らない数学の...
-
婿養子です、妻と離婚して妻の...
-
通学証明書の契印とは
-
よって・ゆえに・したがって・∴...
-
円周率=∞の証明
おすすめ情報