文脈自由言語とはなんですか？

ページ名：文脈自由言語とはなんですか？

A. 文脈自由言語とは、文脈自由文法によって生成される言語で、再帰的な生成規則を持つ言語のことを指します。具体的には、文脈自由文法によって生成される言語は、生成規則が「A」であれば「A」という文字列を生成し、生成規則が「A」であれば「A」という文字列を生成し、というように、再帰的に生成規則を適用することで、無限に文字列を生成することができます。このような性質を持つ言語は、文脈自由言語と呼ばれ、O(n3) の時間で認識されることが知られています。