2.4.2 CS案例

上述的语言生成过程也适用于CS语法,除了有关确定性的那部分。因为在进行中的句子形式绝对不会收缩,所以句子的长度是以单调递增顺序生成的。这意味着如果空字符串不是第一个字符串,那它将再也不会出现了,而且CS语法不会生成ε。此外,如果我们想知道一个给定字符串w是否在语言中,我们可以等着看它是否会出现,如果出现那么答案就是“是”,而如果我们看到生成了长度更长的字符串,那答案就是“否”。

由于CS语言的字符串可以被一个可能的递归算法识别,所以CS语言也被称为递归集