我如何通过构建一个上下文无关的语法来证明这种语言是上下文无关的

Question

如何为以下语言构建上下文无关语法：

L={0^n1^nx|n>=1，并且x∈{0,1}*}

这种语言是一些数量的0后面跟着相同数量的1，然后是一些数量比特串。我在想，对于0^n1^n部分，我需要S->0S1，对于x∈{0,1}*，我需要A->0A|1A|e。由于我需要在相同数量的0和1之后的一些位字符串，所以我做了

S->0S1A|e

A->0A|1A|e

但是语法接受0001101，这是不正确的。有3个0，只有2个1。我是CFG的新手。有人能给我一个关于这种语言的提示吗？

Answer 1

只要有一种语言可以分解为两个子语言的级联，就可以分别构建这两种语言，然后将它们级联：

S → A B
A → …
B → …

在这种情况下，A将是0ⁿ1ⁿ，B将是{0,1}^*。