1

我试图证明以下语言不是上下文无关的:

{a^n b^m a^n b^m : n,m >= 0}

我知道我需要使用抽水引理。所以我必须使用 w = uvxyz where |vy| > 0 和 |xyz| > p(泵送长度)。我知道我需要表明,当为每种情况抽取一个字符串时,它是在语言之外的。

我知道 v^i 或 y^i 包含某些内容而另一个为空但我不知道为我的字符串选择什么的情况。

4

0 回答 0