context-free-grammar - 上下文无关、非上下文无关和常规语法区分

Question

给定{a^(n+m) | n>= 2m}，说明它是常规的、上下文无关的还是非上下文无关的，并使用 DFA、CFG、...

我的回答：它不是上下文无关的，因为没有办法表示 n>=2m。大于号太不明确了。

我想知道我的答案是否正确。

Answer 1

您的答案是* in *正确，因为 a^(n+m) == a^([2m+k]+m) == a^(3m+k) 其中 m, k >= 0。代表这种语言的 CFG如下：

 S->LR;
 R->Ra|a;
 L->LL|aaa;