チョムスキー階層
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/06/19 07:10 UTC 版)
チョムスキー階層（チョムスキーかいそう、Chomsky hierarchy）は、形式言語を生成する形式文法の包含階層（形式言語の階層）で、句構造文法（phrase structure grammar）の階層」などともいう。1956年にノーム・チョムスキーが発表した。
形式文法
形式文法の構成要素は、終端記号（terminal symbol）の有限集合（形式言語の単語で使われる文字）、非終端記号（nonterminal symbol）の有限集合、生成規則（production rule）の有限集合（各生成規則は右側と左側に記号列で構成される単語を含む）、開始記号（start symbol）から構成される。生成規則はある単語に適用され、規則の左側にある単語を右側にある記号列で置換する。導出は一連の規則適用過程である。このような文法で開始記号から始めて生成規則を適用していくことで、終端記号のみから構成される単語を生成する。そのような単語全体の集合が形式言語である。
非終端記号は大文字、終端記号は小文字で表すことが多く、開始記号は 
チョムスキー階層
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/08/15 13:02 UTC 版)
詳細は「チョムスキー階層」を参照 チョムスキー階層は、生成規則による終端および非終端記号からなる文字列の書き換えで定義される、生成文法と呼ばれる形式文法のクラスを軸に定義されている。具体的には、 文字列のいかなる書き換えも許される制限なし文法がタイプ-0、 それぞれの生成規則が非終端記号ひとつのみを書き換える文脈依存文法がタイプ-1、 文脈依存文法のうち前後の文字列に依存せず書き換える文脈自由文法がタイプ-2、 文脈自由文法のうち書き換えが終端記号一つまたは終端および非終端記号一つずつである正規文法がタイプ-3で、 これらの文法によって定義される形式言語がそれぞれ帰納的可算言語、文脈依存言語、文脈自由言語、正規言語である。下方の文法クラスがそれぞれ上方の文法クラスすべての真部分集合となっているため、対応する言語も包含階層が成立する。なお、それぞれに対応するオートマトンもよく知られている。
※この「チョムスキー階層」の解説は、「形式言語の階層」の解説の一部です。
「チョムスキー階層」を含む「形式言語の階層」の記事については、「形式言語の階層」の概要を参照ください。
- チョムスキー階層のページへのリンク
