programming-languages - どうして文脈自由言語でプログラムを書くのですか？チューリング完全であるために、プログラムは再帰的に列挙可能な言語であるべきではありませんか？

Question

ほとんどが文脈自由言語でコーディングしている場合、チューリングマシン（帰納的可算言語を受け入れる）の出力をどのようにシミュレートできるかを本当に理解できません。

Answer 1

プログラムの仕様とその出力を混同しています。

たとえば、帰納的可算言語を受け入れることができるチューリングマシンは、有限遷移関数または「ルールテーブル」によって指定されます。ルールテーブル自体は正規言語で表現できます。

繰り返しになりますが、現代のプログラミング言語の基本的な構文だけが、文脈自由文法によって完全に定義されています。有効なプログラムは、文法では捉えられない多くの条件を満たす必要があります。識別子は使用する前に宣言する必要があり、関数は1回だけ定義でき、プログラムはタイプチェッカーに合格する必要があります。

Answer 2

「ほとんど文脈自由」は、「少し妊娠している」が意味をなさないのと同じように意味がありません。プロパティはそこにあるか、ないかのどちらかであり、私が今まで使用したプログラミング言語では、そうではありません。

しかし、それはあなたがそれらに任意のアルゴリズムを書くことができる理由ではありません。言語のソースコード構文は、特定の文法で記述できる場合とできない場合がありますが、重要なのは入出力の動作です。たとえば、A ^ iB ^ iC ^ iの形式の文字列を出力するプログラムは、これらの文字列が文脈自由言語を形成していなくても、Pascalで記述できます。しかし、これが可能である理由は、Pascal構文が文脈自由よりも強力であるということではありません（それは本当ですが）、それはPascalの構成のセマンティクスです（最終的には、プログラムが実行されるフォンノイマンマシンの概念です） ）。