言語Lは、通常の言語のポンピング補題と文脈自由言語のポンピング補題を満足します.Lについての次の陳述は本当ですか？通常の言語のポンピング補題を満足する言語Lについて、そして文脈自由な言語のポンピング補題についても、何が言えるでしょうか？
A.Lは必然的に通常の言語です。
B.Lは必ずCFLですが、Regularではありません。
C.Lは必然的に非規則的です。
D.いいえ
私は疑問があるところを明確にします。 Lが正規の言語のためのポンプ補題を満たすならば、それは必ずしも規則的ではない。文脈自由と同じです。したがって、それは規則的でも非規則的でもあり得る。 CFLまたは非CFL。答えはBですが、私の意見ではDでなければなりません。
回答Bは間違いなく正しいです。言語Σ *を試してください。これは絶対に規則的かつ間違いなく文脈自由です。また、両方のポンピング補題の条件も満たします。したがって、言語が文脈自由であるが規則的ではないことは間違いない。
両方ポンピング補題は、言語は、規則的または文脈自由であるために必要条件ではなく、これらの言語は、規則的または文脈自由であるために十分条件を与えます。したがって、もし言語が両方のポンプ補助則を通過するならば、それはかもしれないし、文脈自由であるかもしれないかもしれないが、必ずしもそうでなければならないという保証はない。
私はDが正しい選択であると確信しています。
希望すると便利です。
それはpummping補題がするものではありません。これらは通常の/ CFL言語のプロパティとして記述することができます。その場合、その言語はCFと通常の両方であり（これらはそのシナリオの前提条件であるため）、そういう規則的なものでも、CF /規則的でもないその場合、言語はCFではありません（これは非正規であることを含みます）。しかし、問題は、それが話しているポンピング補題のこれらの変形のうちのどれを言うのではない。 – Fizz
@RespawnedFluffあなたが言及しているポンピング補題の変形を見たことがありません（ある言語にいくつかの特性がある場合、間違いなくCFLであると言うもの）。あなたはこれに言及することができますか？私は彼らがどのように動作するのか興味があります。 – templatetypedef
"p implies q"という形式の数学的ステートメントは、 "non-q implies non-p"と再現することができます。ポンピング補題は、後者の形式のプルーフでよく使用されます（R/CFポンピング特性を持たないと、言語がR/CFでないことを意味します）。しかし、簡単なアンケートの後、私は参考文献*に補助声明*として最初の形式（R/CF言語がR/CFポンピング特性を持っています）が優勢であることを発見します。 [コメント長さ制限による次のコメントに続き] – Fizz
Erm ..このサイトは、あなたが知っている無料の宿題を人々にさせる方法ではありません。 –
これは私の宿題ではありません。私はこの疑問を疑っている。私は言語が通常の言語のための補題をポンピングするのを満足すればそれが規則的である必要はないと知っています。 –
"回答はBですが、私の意見ではBでなければなりません。 - 答えがBで、あなたの意見でBでなければ、それが見当たらないように見えますが、何も見当たりません。 – Prateek