1

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

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

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

4

1 回答 1

1

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

 S->LR;
 R->Ra|a;
 L->LL|aaa;
于 2012-03-29T05:51:23.703 回答