ポンピング補題を使用して、言語が文脈自由かどうかを証明するテストが近づいています。練習問題を解こうとしているのですが、うまくいきません...
練習問題は、a)～j)について、次の言語が文脈自由かどうかを証明せよ。文脈自由であれば、それを生成する文脈自由文法を与えてください。
最初の 2 つは次のとおりです。
a) {a^(2i+1) b^(3k+2) c^(4k+3) d^(5i+4) | i >= 0, k >= 0}
b) {a^i b^i c^k d^i | i >= 1, k >= 1}
誰かがこれらの最初の 2 つを解決し、その方法を詳しく説明してくれれば、残り (c から j) を自分で理解できると確信しています。
a は文脈自由です:
A -> aBdddd
B -> aaBddddd
B -> C
C -> bbbCcccc
C -> D
D -> bbccc
B は文脈自由ではありません。だとしましょう。したがって、ポンピング補題が成り立つ整数 p があります。b の次の単語を見てみましょう: a^pb^pcd^p
ポンピング補題によれば、この単語は |vwx| となるシーケンス uvwxy として表すことができます。< p であり、uv^iwx^iy も B にあります。
vx を見てみましょう:
ケース 1: vx に「c」が含まれている。その場合、uwy も B にあるはずですが、B には少なくとも 1 つの "c" が必要です。だからそのケースはありえない。
ケース 2: vx に「c」が含まれていない。"a"、"b"、または "c" のうち最大 2 つを含む必要があります (そうでない場合、|vwx| は p より多くなります)。したがって、uv^2wx^2y には同数の a、b、c が含まれず、B にも含まれません。
したがって、B は文脈自由言語ではありません。