后规范系统

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型语法。