私は現在、チョムスキーのヒエラルキーと、ヒエラルキーの各レベルを認識するオートマトンのタイプを学習する離散数学テストの勉強をしています。ほとんどのコンピューター言語は階層の「レベル 2 と 1」に分類されると教えられていますが、正確にはそうではありません。
私の質問は次のとおりです。
各レベルに属する機能は?
これは理論的根拠にすぎませんか？Dennis Ritchie や James Gosling のような言語設計者は、C や Java を設計する際にこの点を考慮する必要があったのではないかと思います。彼らは？誰かがこれをどのように適用しますか?
チューリング マシンは階層のレベル 0 を認識していると言われています。もしそうなら、レベル0に属する言語機能はありますか? これはもしかしたら自然言語処理なのかもしれませんね。
なし。レベル 1 にはレベル 2 が含まれています。
レクサーとパーサーの設計に役立ちます。C の作成者がそのことを考えていたかどうかはわかりませんが、Java は確かにそうです。パーサージェネレーター
チューリングマシンは、計算できるものなら何でも計算します。「計算可能」は次のように定義されています: チューリング マシンによって受け入れられる可能性があります。もちろん、これには自然言語処理も含まれます。レベル 2 を超えるものは、言語生成にはあまり役に立ちません。そのような入力を読み取るプログラムは停止しない可能性があるためです ( Word Problemはもはや解決できません)。
タイプ 3 文法は通常の言語を生成します。これらは、「xxx」で始まる、「xxx」を含む、「xxx」で終わる、奇数の y を含むなどの機能を持つ言語です。有限オートマトン (決定論的または非決定的) はこれらの言語を認識します。
タイプ 2 文法は文脈自由言語を生成します。これらは、ある数の x の後に少数、またはそれ以上、または同数の y が続く、または単語の後に同じ単語が続くが逆になるなどの機能を持つ言語です。プッシュダウン オートマトンはこれらの言語を認識します...スタックを使用した有限オートマトンを考えてみてください。
タイプ 1 文法は、文脈依存言語を生成します。これらはタイプ 0 の文法に非常に近いため、両者の違いを見つけるのは難しいことがよくあります。LBA (線形有界オートマトン) はこれらの言語を認識します。リソースが限られているチューリング マシンを考えてみてください...現代のコンピューターを考えてみてください。
タイプ 0 文法は、再帰的に列挙可能な言語と呼ばれることもあるチューリング言語を生成します。これらは基本的に、コンピュータ プログラムを記述して認識できる言語であれば何でも構いませんが、実際のコンピュータには一般にある種のメモリ制限があるため、タイプ 1 と実際に混ざり合っています。
有限オートマトンとプッシュダウン オートマトンは、コンパイラを作成するときに発生する問題を解決する上で非常に重要です。ただし、それがそれらを研究する理由ではありません。計算できる/できないものの限界を知るためにそれらを研究します。多くのプログラマーは、コンピューターを使えばどんな問題でも解決できると考えています。計算可能性理論はそうではないと教えてくれます。
Edit by "Dude" - OK、これはわかりやすい (そして有名な) 問題で、チューリング マシン、コンピューター、プログラマー、エイリアンの天才では解決できません...
いくつかのドミノがあると想像してください...しかし、ドットのパターンの代わりに、上部と下部に短い単語があり、「aba」や「cab」などの単語を言います。これらのドミノを 5 個、10 個、または 50 個あげるとしたら、一番上の単語をすべて連結して、一番下の連結した単語と正確に一致するように並べてもらえますか。どのドミノも好きなだけコピーできます。
ドミノの例 (考案:) (a/aab)、(aba/ac)、(cab/ab) は、上 (a+aba+cab) が下 (aab+ac+ab) と正確に等しい 3 つのドミノのセットです。 .
これは簡単に聞こえるかもしれませんが、一般的に解決することはできません。
ところで、私が最初にこの問題を読んだ/理解したとき...私は考えていました....ああ、n! よく見え始めています！