context-free-grammar - 文脈自由、非文脈自由、通常の文法の区別

Question

が与えられ{a^(n+m) | n>= 2m}たとき、それが規則的か、文脈自由か、文脈自由でないかを述べ、DFA、CFG などを使用して証明します。

私の答え: n>=2m を表現する方法がないため、コンテキスト フリーではありません。大なり記号があいまいです。

私の答えが正しいかどうか疑問に思っています。

Answer 1

a^(n+m) == a^([2m+k]+m) == a^(3m+k) ここで、m, k >= 0 であるため、あなたの答えは * in *correct です。そのような言語を表す CFG以下のとおりであります：

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