オートマトン

質問

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

という問題の解答が分かりません。
どなたか教えてください。

回答No.5

stomachman · ベストアンサー

ま、ヒント出しますか。

●問(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

stomachman

ANo.2へのコメントについてです。

> 判断すればいいのでしょうか。

　「いいのでしょうか」と仰るということは、どうも「正当性」の意味もお分りでない？

　何かアルゴリズムAを考えたのなら、「AがどんなMについても正しい結果を与える」ということの証明を試みる。もし証明できたら、それが「Aの正当性を示した」ということです。一方、Aが正しい結果を与えないようなMの存在がもし証明できれば、「AはL(M)=Øとなっているかどうかを判定するアルゴリズムではない」ということが分かり、つまりAは落第。

　だから、「いいのでしょうか」と尋ねて「いいです」とか「だめです」という答を貰ったって、レポートにはならんのです。

　それはさておき、まずはQ, Σ, δ, q, F, L(M)って一体何の事なのか、補足なさって下さいな。もちろん、名称を訊いているんじゃありませんよ。「どんなMについても」ということを考えるためには、何がMで何はMでないのか、つまり「決定性有限オートマトンM」というものがどう定義されているのか、明確に把握しないと話が始まらないんです。

回答No.3

Tacosan

「L(M)=Ø」は「Mによって受理される言語がない」ということではありません. 前者は「M によって受理される言語が『空集合』である」という意味です. あくまで「『空集合』として存在する」であって「存在しない」ではありません.

で「(ある語が) Mによって受理される」の意味は分かりますか?

回答No.2

stomachman

ANo.1へのコメントについてです。

> Mによって受理される言語をL(M)と書く。

「Mによって受理される」とはどういう意味で、「言語」とは何の事か、お分かりならば(1)が出来ないはずはないと思うんですが…
どこで分かんなくなったのか、説明して下さいな。

補足

もとの問題文は、「L(M)=Øとなっているかどうかを判定するアルゴリズムを与え、その正当性について議論せよ」というものだったのですが、これはMによって受理される言語がないということと解釈してそう書きました。

どこで分からなくなったというより、何をすればいいのか分からない感じです。
受理する言語がないかどうかは、オートマトンに初期状態と最終状態が存在するかどうかを判断すればいいのでしょうか。
これがきかれていることに対する答えなのかがよくわかりません。

回答No.1

stomachman

「(1)が分からんというのは、そもそも『有限オートマトン』や『言語』が何のことなのかを知らないということではないか？」と言われたってしょうがないような質問ですよ？
　これじゃ、説明しようにも用語がどれだけ質問者氏に通じるのか分かりませんので、まずは

> 決定性有限オートマトンM1=(Q1,Σ,δ1,q1,F1)

のQ1,Σ,δ1,q1,F1がそれぞれ何のことで、他の要素とどう関係するのか、そして、「受理される言語」L(M1)が何のことなのかを、補足に書いてくださいな。

補足

すみませんでした。

決定性有限オートマトンをM=(Q,Σ,δ,q0,F)と書く。
ここで、Qは状態の有限集合、Σは有限の入力アルファベット、δ:Q×Σ→Qは状態推移関数、q0は初期状態、Fは受理状態の集合とする。
Mによって受理される言語をL(M)と書く。

と問題の最初に書くべきでした。
よろしくお願いします。