これは正しいです：タイプ3の文法が$ \ sigma ^ * $を生成するかどうかはc.eではありません。

Question

Sipserの本からの例では、計算理論の紹介は、 $ tm $ に対して決定できないことを示しています。数学コンテナ "> $ cfg $ （またはタイプ2文法）は $ \ sigma ^ * $ を生成します。ここで、 $ \ sigma $ はアルファベットです。この言語を呼び出す $ cfg_ {all} $

しかし上記の言語も計算可能に列挙できない。 $ cfg_ {all} $ から $ \ bar {a_ {a_ {a_ {tm}}} $ $ \ bar {a_ {tm}} $ は言語STです入力 $ tm $ は入力を受け付けません。 $ \ bar {a_ {tm}} $ は、計算可能に列挙できません。

しかし、タイプ3の文法が $ \ sigma ^ * $ を生成するかどうかはc.eではありません。 ？ （タイプ3の文法は文脈のない文法のサブセットです）。有限オートマトンが $ \ sigma ^ * $ を認識できることは事実ですが、この言語はタイプ3の文法が $ \ sigma ^ * $ ？

私の混乱の原因を明確にするために、まとめて、プッシュダウンオートマトンが $ tm $ に指定できます。 -container "> $ \ sigma ^ * $ または入力を受け入れますが、 $ tm $ に対して決定的でも計算可能に列挙できないCFGは $ \ sigma ^ * $ を生成します。同様に、有限オートマトンが $ \ sigma ^ * $ $ tm $ に対して決定できます。 >しかし、 $ tm $ には決まっていないかもしれません。 $ 。認識と生成の違いはどういうわけか。

編集： $ \ sigma ^ * $ を認識するためのプッシュダウンオートマトンのための明らかに

Answer 1

タイプ3の文法（通常）が $ \ sigma ^ * $ を生成するかどうかを確認するには、言語を受け入れる最小DFAをビルドして、それが初期であるかどうかを確認します。=最終状態、すべてのシンボルのループ。含まれるすべての構造は効果的です。