チョムスキー階層 - Wikipediaチョムスキー階層（チョムスキーかいそう、Chomsky Hierarchy）は、形式言語を生成する形式文法の包含階層（「形式言語の階層」）で、「句構造文法（Phrase Structure Grammars）の階層」などとも言う。1956年にノーム・チョムスキーが発表した。 形式文法[編集] 形式文法の構成要素は、「終端記号」（Terminal Symbols）の有限集合（形式言語の単語で使われる文字）、「非終端記号」（Nonterminal Symbols）の有限集合、「生成規則」（Production Rules）の有限集合（各生成規則は右側と左側に記号列で構成される単語を含む）、「開始記号」（Start Symbol）から構成される。生成規則はある単語に適用され、規則の左側にある単語を右側にある記号列で置換する。導出は一連の規則適用過程である。このような文法で開始記号から始めて生成規
