計算理論についての質問

質問

計算理論についての質問です。

文脈自由文法gがεを受理するかどうかを判定するアルゴリズムが必ず存在するか、しないかを証明するという課題が出たのですが、
「アルゴリズムが存在する」ということはどうやったら証明できるのでしょうか？

今、手元にはホップクロフトの「オートマトン言語理論計算論」があるのですが、「アルゴリズムが存在するかどうか」を証明するような問題が見つかりません。
学校でもこのような問題の例題はやっていないので、どなたか教えてください。
よろしくお願いしますm(__)m

回答No.1

knztc · ベストアンサー

＞文脈自由文法gがεを受理するかどうかを判定するアルゴリズムが必ず存在するか、
＞しないかを証明するという……

任意の文脈自由文法 G に対し、G が 文字列 w を生成するか否かを判定するアルゴリズム
は存在します。
すなわち、G が w を生成するか否かを判定するチューリング機械を
設計することが可能です。

＞「アルゴリズムが存在する」ということはどうやったら証明できるのでしょうか？

チューリング機械が設計可能であることをいえばよいです。
与えられた文脈自由文法 G が w を生成するか否かを判定するアルゴリズムが存在
することの証明は、たとえば、
「計算理論の基礎」(共立出版)
に載っています。

回答No.2

a-saitoh

証明といえばだいたい二つの方法があります。
・アルゴリズムが存在しないと仮定して、矛盾を導く
・アルゴリズムを実際に一つ示す

この問題では後者でいいのでは？
一般性を失わずに、gが　○○標準形で定義されているものと仮定する。・・以下略・・・
てな感じですね。