喬姆斯基分類

喬姆斯基分類(Chomsky classification)亦稱喬姆斯基層次一種分層方法.是喬姆斯基(Chom-sky, N.)於1959年提出的關於形式語言及其文法的分層方法.

喬姆斯基把文法定義為四元組G=+ ',V,S,P)，其中藝是終結符號集，V是非終結符號集，S是開始符號，屍是變換規則(又稱產生式)集.這裡的},V,P都是有限集，乏自V=必(必表示空集合),SEV.若令aE (}UV)+, /3E (}UV)'(用+代替，表示不含空字)，則屍中所有的產生式皆形如a->月，表示a由月組成或用月替換a.這樣定義的文法稱為喬姆斯基文法，有時也稱為短語結構文法或無限制文法.對文法產生式作某些限制，可以得到生成能力各不相同的幾類文法.