有没有办法为这种语言创建类型 3 语法？
Is there a way to create a type 3 grammar for this language?
我正在尝试为该语言寻找最高类型的语法：
L={0^2n 1^(n-1)|n>=1}
我只设法做到了这一点：
S->00X
X->00X1|λ
这不是类型 3。我似乎无法弄清楚如何让它成为类型 3（如果可能的话）。
你做不到，因为L不是正规语言。
假设 L 是正则的。设 w = 0^(2p)1^(p-1) 为某个整数 p>=1，因此 |w| > p。此外，考虑字符串 x、y 和 z，使得 w = xyz 和 |xy| <= p，这意味着 x 和 y ] 是 0 的序列（因为 p < 2p）。根据抽取引理，xy^nz 形式的任何字符串在 L 中也是 also，但这意味着我们可以增加 0 的数量而不增加 1 的数量在 z 中找到。因此，我们假设 L 是正则的一定是错误的。
我正在尝试为该语言寻找最高类型的语法：
L={0^2n 1^(n-1)|n>=1}
我只设法做到了这一点：
S->00X
X->00X1|λ
这不是类型 3。我似乎无法弄清楚如何让它成为类型 3（如果可能的话）。
你做不到，因为L不是正规语言。
假设 L 是正则的。设 w = 0^(2p)1^(p-1) 为某个整数 p>=1，因此 |w| > p。此外，考虑字符串 x、y 和 z，使得 w = xyz 和 |xy| <= p，这意味着 x 和 y ] 是 0 的序列（因为 p < 2p）。根据抽取引理，xy^nz 形式的任何字符串在 L 中也是 also，但这意味着我们可以增加 0 的数量而不增加 1 的数量在 z 中找到。因此，我们假设 L 是正则的一定是错误的。