automata - 言語が文脈自由であることを一目でどのように判断できますか?

Question

私の教授は、与えられた言語が規則的か、文脈自由だが規則的ではないか、または文脈自由でないか (つまり、PDA を描画したり、文脈自由文法を書いたり、文脈にポンピング補題を使用したりすることなく) を迅速に判断することを期待しています。 -無料の言語)。

通常の言語が何であるかを一目ですばやく判断するのに役立つヒントは知っていますが、言語が文脈自由であるかどうかはわかりません。

ありがとうございました。

Answer 1

もちろん、普遍的な答えはありません。ただし、CF が実行できる、または実行できない一般的なパターンがいくつかあり、さまざまなバリアントに表示されます。CF でできること (および REG ではないこと):

• a^nb^nのように2か所で同時に数える、
• a^nb^na^mb^m のように繰り返し
• または a^nb^ma^mb^n のようにネスト
• 回文パターン、つまり w の後に w の逆が続く
• 「a と b の数が等しい単語」や「b よりも a が 5 個多い単語」のように、ある文字の数を別の文字に対して数えます。

CF が実行できない典型的なこと:

• a^nb^nc^n のように 3 か所で同時に数える
• a^nb^ma^nb^mのように交差する2組の場所で同時に2回数える
• 二部注文したみたいww
• 「a、b、c の数が等しい単語」のように、3 文字の数を比較します。

これらのパターンを念頭に置いて、最も一般的なサンプル言語の文脈自由度を判断できるはずです。