チョムスキー階層
チョムスキー階層（チョムスキーかいそう、Chomsky hierarchy）は、形式言語を生成する形式文法の包含階層（形式言語の階層）で、句構造文法（phrase structure grammar）の階層」などともいう。1956年にノーム・チョムスキーが発表した。
形式文法
詳細は「形式文法」を参照
形式文法の構成要素は、終端記号（terminal symbol）の有限集合（形式言語の単語で使われる文字）、非終端記号（nonterminal symbol）の有限集合、生成規則（production rule）の有限集合（各生成規則は右側と左側に記号列で構成される単語を含む）、開始記号（start symbol）から構成される。生成規則はある単語に適用され、規則の左側にある単語を右側にある記号列で置換する。導出は一連の規則適用過程である。このような文法で開始記号から始めて生成規則を適用していくことで、終端記号のみから構成される単語を生成する。そのような単語全体の集合が形式言語である。
非終端記号は大文字、終端記号は小文字で表すことが多く、開始記号は 
- Chomsky hierarchyのページへのリンク
