PSG、CSG、CFG和RLG分别是什么

本节主要讨论四种不同类型的文法体系及其区别：短语结构语法（PSG）、上下文相关语法（CSG）、上下文无关语法（CFG）以及右线性规则（RLG）之间的差异。

Part 2 概念

文法G=(V，T，P，S)

G 被称为 0 型文法（type 0 grammatical system），它也被视为短语结构文法（phrase-structured grammar, PSG）。

L(G)被称作0型语言。另一种说法是短语结构语言和递归可枚举集。相应的识别该语言的机器是图灵机（TM缩写为turing machine）。

L(G)被称作0型语言。另一种说法是短语结构语言和递归可枚举集。相应的识别该语言的机器是图灵机（TM缩写为turing machine）。

G是0型文法。

当且仅当对于任意字符串α到β属于集合P，并且满足其长度关系：即$|\beta|\geq|