此常规语言的标签正确吗？

Question

所以我是一名计算机科学新手，希望社区提供一些帮助来帮助我理解这个主题。

我有这种常规语言，我试图从这种语言中确定 3 件事：

DOUBLE = {w | w contains twice as many 0s as 1s}

• 不规则
• 上下文无关
• 可判定

我对每个问题的想法是

由于泵引理，

它不规则。为了矛盾起见，假设 DOUBLE 是正则的。如果我们使用字符串

\(0^n1^n\)

那么对于这三个条件。

1. |xy| ≤ n

2. |y| > 0

3. 对于所有整数 i ≥ 0，字符串

   xy^iz

   也在 L 中。 应用泵引理时，泵引理不起作用

是上下文无关的，因为如果我们使用类似于

S -> 0S1S | ε

的上下文无关语法（CFG），生成的字符串中 0 的数量是 1 的两倍

是可判定的，因为它包含的 0 是 1 的两倍

Answer 1

• 由于你所说的原因，不正常
• 不是上下文无关的（用这个工具测试你的尝试，你会发现它也匹配“01”，其中0的数量不超过1的两倍）。一般来说，上下文无关语法不能无限地“计数”，你需要一个下推自动机来实现这一点
• 是可判定的，因为您可以通过计算数字轻松地编写算法来接受/拒绝字符串