如何通过构造上下文无关文法来显示该语言是上下文无关的？

Question

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

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

这种语言是一定数量的零，后跟相同数量的1，再加上一定数量的位串。我在想我需要S-> 0S1作为0 ^ n1 ^ n部分，A-> 0A | 1A | e代表x∈{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} ^*。