关于语言DOUBLE的非正则性、上下文无关性及可判定性的验证问询

你提出的语言定义为：DOUBLE = {w | w包含的0的数量是1的两倍}，以下是对你三个属性推理的验证：

1. 非正则性 #

你的核心思路用泵引理证明是对的，但选择的测试字符串有误：你用的0^n1^n中0和1数量相等，并不属于DOUBLE，无法用来验证该语言的正则性。

正确的做法是选择属于DOUBLE的字符串，比如0^{2n}1^n（n取大于泵长度p的值）。假设DOUBLE是正则语言，根据泵引理，该字符串可拆分为xyz满足：

• |xy| ≤ p
• |y| > 0
• 对所有i≥0，xy^iz∈DOUBLE

由于|xy| ≤ p ≤ n，y只能由0组成，设y包含k个0（k>0）。当i=2时，xy^2z包含2n +k个0和n个1，此时0的数量不再是1的两倍（2n+k ≠ 2n），因此该字符串不属于DOUBLE，与泵引理矛盾，故DOUBLE非正则。

2. 上下文无关性 #

你给出的CFGS -> 0S1S | ε是错误的，这个文法生成的字符串中0和1的数量始终相等（每生成一个0就对应生成一个1），无法得到0数量是1两倍的字符串。

正确的上下文无关文法可以设计为：

S → 00S1 | 0S01 | S001 | ε

这个文法每次扩展时都会新增两个0和一个1，最终生成的字符串必然满足0的数量是1的两倍，因此DOUBLE是上下文无关语言。

3. 可判定性 #

你的推理完全正确：对于任意输入字符串w，只需统计其中0的数量c0和1的数量c1，判断是否满足c0 = 2*c1即可。我们可以构造一个图灵机完成这个统计和判断过程，因此DOUBLE是可判定语言。

内容的提问来源于stack exchange，提问作者cool cat