grammar - この言語のオートマトンを見つける必要があります

Question

次の言語を決定するための文法またはオートマトンを見つけるのを手伝ってください。

a ⁿ b ⁿ c ⁿここで、n≥1

Answer 1

この言語は、文脈自由言語のポンピング補題に失敗します(実際、この言語は CFL ポンピング補題の例として使用されます)。したがって、通常でも文脈自由でもありません。あなたの最善の策は、チューリングマシンを使用することです。

それは間違いなく決定的な言語です。うまくいけば、使用するオートマトンのタイプを知ることで、自分で問題を見つけるのに役立ちます。これは宿題のように見えるので、それが最も手がかりになります。