Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
给定{a^(n+m) | n>= 2m},说明它是常规的、上下文无关的还是非上下文无关的,并使用 DFA、CFG、...
{a^(n+m) | n>= 2m}
我的回答:它不是上下文无关的,因为没有办法表示 n>=2m。大于号太不明确了。
我想知道我的答案是否正确。
您的答案是* in *正确,因为 a^(n+m) == a^([2m+k]+m) == a^(3m+k) 其中 m, k >= 0。代表这种语言的 CFG如下:
S->LR; R->Ra|a; L->LL|aaa;