文脈自由文法G=({S},Σ,P,S) が L(G)={0 ^n 10^n ∣n≥0} を生成する。ただし、{S} は G の非終端記号の集合である。 このとき、L{G}が正則言語ではないことを以下のように証明しました。 証明に慣れていなくて、間違っている気がするので、間違いがあれば教えて欲しいです。 L{G}が正則言語であると仮定する。ポンピング補題により、L{G}のみに依存する正整数pが存在して、w=0^p 10^p∈L{G}を取り、w=xyz ,p≥|xy| ,|y|>0とできる。 ここで、xy^2 zはp≥|xy|より、yには0しか含まれないことになる。したがって、xy^2 zは中央の1をはさんで0の個数が一致しなくなるため、xy^2 z∉L{G}となる。しかし、これはポンピング補題に矛盾するため。L{G}は正則言語ではない