context-free-language - これは文脈自由言語ですか、それとも文脈依存言語ですか?

Question

Formal Languages と Automata Theory を勉強していますが、本の中で答えられていない問題について質問があります。質問は：

この言語はコンテキストフリー、レギュラー、またはコンテキストセンシティブですか?

L={a^ib^jc^k|i<=j または j<=i , j=k}

Answer 1

文脈依存です。

Not Regular : 有限状態マシンではできない b または c の出現回数を覚えておく必要があります。

ポンピング補題を適用するかのように、文脈自由ではありませんa^{2}b^{2} b^{n-4}b^{2}c^{n}。

したがって、文脈依存です。