但是，典型的构造并不是排列组合

yushan

《表达的探究》书摘：

　　　　　　　　　第二章 构造点评

# `' J( F- l- P: P) r

构造与简单枚举相比，具有后组灵活性，基坐标和幂集合就是两个样本。但是，典型的构造并不是简单的排列组合，而是有组织结构的。比如自然语言就不是词汇的简单排列，而是有文法的句子构造。“组合”与“聚合”，“替换”、“分布”和“扩展”，还有“文法产生式”，这些概念都是对语言结构的描述。

结构改变了字符序列的线性关系，大大增强了表现力。一个树形的层次结构，同一层次不同节点的下属单元之间不直接交换信息，因此简化了信息交换的复杂性；同理，一个分“块”的网络结构，“块”的内部单元也不与其他“块”的内部直接交换信息。所以，层次与“块”都形成了中间状态变量，这样就为形成新的语义关系提供了基础，同时它们也都有信息简化和信息屏蔽作用。上下层次的树与分块的网络，这两种结构在构造表达上也具有等效性。

5 A/ ^1 t& _8 Y) s5 A. M7 q

构造表达既可以自上而下分解，也可以自下而上还原。递归函数具有自下而上性，形式语言的文法推导式具有自上而下性，这两者又可以从k阶相关上找到共同点。形式语言的四种文法，就是从相关性这一最宽泛的角度对字符串结构特征所作的分类。构造表达的另一个数学模型是自动机，自动机提供了输入、状态、输出三个平面之间关系的表达。中间状态平面对外部输入输出提供了解耦的缓冲空间，提供了排序的新基底，从而形成了以内部状态不变，应外部输入/输出万变的空间表达方法。可计算理论证明：自动机模型，递归函数和形式语言文法这三者是等价的，都可以用“可计算”这一概念来刻画。

从排序的观点来看构造，递归是最典型的排序方法，它通过不断吸收独立因素作为基底，归纳出一般的通项关系式。不可递归就是不可排序，就是广义的不可度量。字符串的周期循环，是递归性的一个特例。周期性对有序与无序提供了很直观的量化描述。从混沌序列的例子可知，在一个区间内，存在着具有无数个循环周期的字符串，它既是复杂性的，也是随机性的，这揭示了有序与无序的不可判定性。

@7 O! }' j# D! d9 N* w' O# A

许多案例说明：在一定情况下，时序的串联构造与空间的并联构造之间，是可以相互替换相互转换的。针对某一对象模式，一般而言，基元硬件与构造软件这两者在表达中的复杂性常常是相互制约的反比关系。但是，对基元的模糊化处理可能会打破这种制约。一个对象模式在表达上的“复杂性”是难以判定的，这显然与选用的软、硬件搭配有关，也就是与排序方法有关。序列的复杂性找不到统一的元评测标准，绝对的最佳软、硬件搭配方案并不存在，这是一个非常重要的结论。

/ {3 ^! K# X6 I: @( G3 ^

详细信息可见表达的探究网站：

www.yushan58.blogchina.com

' O7 X. M/ n- f. L+ V; t- @' C2 o

[em01][em01][em01]

gssdzc

非常感谢。顶起来

翼点通

啊~~~~~~~~~