理论：给定的语言环境是否是免费的？

Question

在最近的测试中，有人问我承认，如果下面的语言是上下文无关：

据对我来说，它是免费的情况下，可通过下面的上下文无关文法，其中被接受S是开始符号和Y是一个非终端：

然而，我的回答被认为是错误的，那么显然这语言不是上下文。

我对自己的回答充满信心，但回复让我感到困惑。我的理解是否正确？请让我知道我是否遗漏了一些东西。

Answer 1

该语言不是上下文无关的语言！你的语法错了！

根据语言描述0 s后缀应该小于1 s的数字和前缀0 s。但是，使用你的语法，您可以生成错误的字符串，如下所示：

第一步：总是由S0
第二步替换S：现在更换S到Y

S --> S0 --> S00 --> S000 --> Y000 

现在可以更换Y到^（NUL）它给出000，这个字符串不在你的语言中。

或者更换Y到0Y1然后Y到^：

Y000 ---> 0Y1000 ---> 01000 

01000字符串不是语言。所以你的语法不会生成相同的语言。