コンテキストフリーで、すべての通常の言語を生成できますか？

Question

I現在「 CFGはまた、定期的な言語を作成することができ」、または、それはすべてのCFGする必要があり、私は声明に出くわした計算理論を勉強していますが（任意の）すべてを作成することができ、通常の言語

Answer 1

私は、これはより多くのだと思いますコンピュータサイエンスの質問よりも、言葉の問題です。つまり、ここには、私が伝えようとしていると思われるものをより明確に定式化することができます：

普通の言語では、その正規言語を生成する文脈自由文法があります。

これを確認するには、正規の文脈自由文法をまず構築します。私たちは、RLの標準的なCFGとして正しい規則的な文法を取るかもしれません。私はその構築について詳細には触れませんが、言語のDFAがわかっていて、その生産がオートマトンの遷移を反映するCFGを生成すると仮定します。

任意のRLに対して単一のCFGが存在すると仮定すると、任意のRLに対して無限に同等のCFGが存在することを直ちに知ることができます。

Answer 2

実際、REGはCFのサブセットです。したがって、すべての通常の言語は文脈自由であり、CFGによって生成することができます。