喬姆斯基分類

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

基本介紹

• 中文名：喬姆斯基分類
• 外文名：Chomsky classification
• 提出者：喬姆斯基
• 類型：喬姆斯基層次一種分層方法

喬姆斯基把文法定義為四元組G=(Σ,V,S,P)，其中Σ是終結符號集，V是非終結符號集，S是開始符號，P是變換規則(又稱產生式)集.這裡的Σ,V,P都是有限集，Σ∩V=∅(∅表示空集合),S∈V.若令α∈(Σ∪V), β∈ (Σ∪V)*(用+代替*表示不含空字)，則P中所有的產生式皆形如α→β，表示α由β組成或用β替換α.這樣定義的文法稱為喬姆斯基文法，有時也稱為短語結構文法或無限制文法.對文法產生式作某些限制，可以得到生成能力各不相同的幾類文法.