次の言語が文脈自由（ではない）であることをどのように示すことができますか？規則的ではないという議論は次のようになります。
この言語は文脈自由だと思います...私がこれを考える理由は、L = {a n b m c {n + m} | n、m>=0}は文脈自由です。これの証拠はで見つけることができます
http://cg.scs.carleton.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf（pdfのp102、テキストのp94）
証明は一種の長さであり、PDAとの同等性を利用することで、おそらくはるかに短く証明できます（つまり、最初にいくつかのシンボルをスタック上でn "+" m回押し、その結果、再びn + m回離します）。いずれにせよ、この例は、私の元の言語も文脈自由でなければならないと私に信じさせます。それでも、私はこれについてどのように議論できるのか本当にわかりません。
いいえ、あなたの仮定は正しくありません！
言語L = { x = y + z | where x, y, z are binary integers and x is the sum of y and z}は文脈自由言語（CFL） ではありません。
説明しようと思います。
まず、次のs言語の文字列の例を検討してLください。
110 = 100 + 10
1110 = 1100 + 10
:
111000 = 110000 + 1000
私の説明では、LHSがX問題であり、RHSは Y + Zです。
CFLの補題のポンピングとは何ですか？
言語Lが文脈自由である場合、|s|を持つL内の任意の文字列sが存在するような整数p≥1が存在します。≥p。（ここで、pは「ポンピング長さ」は次のように書くことができます。
s = uvxyz
with substrings u, v, x, y and z, such that
1. |vxy| ≤ p,
2. |vy| ≥ 1, and
3. uv nxy nz is in L for every natural number n.
この定義| ≥1、および3。uvnxy nzは、すべての自然数nに対してLになります。
注意：ポンプの長さより大きくないs、の中央部分。（条件1） vxyp
[解決策]：
条件を満たす 文字列sを選択しましょうL|s| ≥ p
私たちの sは1m0 q = 1 m -1 0 q + 10 q 、ここで q > p , m-1 > p
現在、の全長sは 2m + 2q -1それよりも長く、pもちろん、自然数のいくつかの組み合わせでは、この不等式が可能です（私は長さを含めず、+説明=を簡単にします）
現在、私たちsは言語であり、CFGの反復補題に従って十分に大きいです。
今それを破る：
u vxy z = 1 m 0 q = 1 m-1 0 q + 10 q
言語Lで新しい文字列を見つけてポンピングして生成するようにしてくださいv。ただし、 （条件1によると） それよりも遠くないように注意してください。yvyp
言語で新しい文字列を生成できるようにする ための選択肢はv ありません。y
（ステップ1）：増加することを選択した場合、LHSの最後がRHSの最初（> p）にあるため、RHS1とLHSの両方をポンピングできないためです。したがって、言語で新しい文字列を生成することはできません。 =1q1
（ステップ2）： m-1（> p）のLHSの最後がRHSの最初に膨張するため、LHSとRHSを一緒0に増やすことができないことを再度ポンピングしたいとします。 000
（ステップ3）：111...000... 両側の組み合わせをポンピングすることはできません。、これを試してみると、言語Lから文字列が取得されます。
補題の規則の範囲内で他のオプションも試してください。vとの正しい選択は見つかりませんy。
[答え]
したがって、彼はsLに十分な大きさの文字列を持っており、それを使用して言語で新しい文字列を生成することはできません。したがって、CFLの反復補題との矛盾はCFLLではありません。