后規范系統
編輯Postcanonicalsystem,又稱Postproductionsystem,由EmilPost創造,是一種字符串處理系統,它從有限的許多字符串開始,通過應用有限的j套特定形式的規則對它們進行反復轉換,從而生成一種形式語言。因為每一個Post典范系統都可以簡化為一個字符串重寫系統(semi-Thue系統),這是一個更簡單的表述。這兩種形式化都是圖靈完全的。
后規范系統的定義
編輯一個Postcanonical系統是一個三聯體(A,I,R),其中A是一個有限的字母表,A上的有限(可能是空的)字符串被稱為詞。I是一個有限的初始詞集。R是一個有限的字符串轉換規則集(稱為生產規則),每個規則的形式如下:↓其中,每個g和h是一個指定的固定詞,每個$和$'是一個變量,代表一個任意詞。生產規則中箭頭前后的字符串分別稱為該規則的前因和后果。要求后果中的每一個$'都是該規則前因中的$之一,而且每個前因和后果都至少包含一個變量。其元素是初始詞和所有通過重復應用生產規則可以得到的詞。這樣的集合是可遞歸列舉的語言,每一種可遞歸列舉的語言都是某個這樣的集合對A的一個子字母的限制。例子(良好形式的括號表達)字母表。{[,]}初始詞:[]制作規則:(1)$→[$](2)$→$$(3)1$2→1[]2在格式良好的括號表達式的語言中推導出幾個詞。
正常形式定理
編輯如果一個Postcanonical系統只有一個初始詞,并且每個生產規則都是簡單的形式,那么就可以說它是正常形式的。{displaystyleg$rightarrowh}1943年,Post證明了顯著的正常形式定理,該定理適用于最一般類型的Post經典系統。給定字母表A上的任何Post經典系統,可以從它構建一個正常形式的Post經典系統,可能會擴大字母表,這樣,由正常形式的系統產生的只涉及A的字母的詞集,正是由原始系統產生的詞集。構成通用計算模型的標簽系統是后正常形式系統的明顯例子,也是單基因的。
(如果給定任何字符串,在一個步驟中最多可以從它產生一個新的字符串,即該系統是確定性的,那么一個典型的系統就被說成是單基因的。)字符串重寫系統,0型形式語法字符串重寫系統是一種特殊類型的Post經典系統,也就是說,每個生產規則都是一個簡單的替換規則,通常寫成g→h的形式。已經證明,任何Postcanonical系統都可以還原為這樣一個替換系統,作為一種形式語法,它也被稱為短語結構語法,或者喬姆斯基層次結構中的0型語法。
內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/164033/