如何通过树限制的一般语法展示金属线性和规律性

本文介绍了一般语法的导出树。在这些树中，它定义了上下文相关的节点对，对应于使用非上下文无关规则重写两个相邻符号。证明了如果存在一个常数u，使得生成语言中的每个句子w都是一个导出树的前沿，其中任何相邻路径对包含u个或更少的上下文相关节点对，那么具有慢分支导出树的线性核心一般语法生成的语言是k线性的。接下来，证明了如果存在一个常数u，使得生成语言中的每个句子w都是一个导出树的前沿，其中任何相邻路径对包含u个或更少的上下文相关节点对，那么具有规律核心的一般语法生成的语言是规律的。本文解释了这一结果是展示某些语言是k线性或规律性的强大工具。