理論：給定的語言環境是否是免費的？

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字符串不是語言。所以你的語法不會生成相同的語言。