WはWがどこに属しているのですか？{a、b} *文脈自由な言語ですか？ Wは、{A、B} *文脈自由言語に属しているところ

Question

はWWますか？ はいの場合は、PDAをご用意ください。

Answer 1

はありません、それは矛盾のために、それがあること、それを受け入れるPDAがありません

想定しています。

（のCFG用）ポンプの補題によると、すべての単語（私たちはすぐにものを選択します）sためのいくつかの部分文字列がu,v,w,x,yようs=uvwxyとがあるpような長さがあります：

1. |vwx|<=p
は、
2. |vx|>=1
3. uv^n wx^n y は、任意の正n

するための言語であります

の単語a^p b^p a^p b^pを考えると、このようu,v,w,x,y

どちらのvwxは、単語の途中が含まれているか、それは完全に前半に記載された、またはそれは完全に後半に含まれています。

それは言葉uv^2 wx^2 yで、その後、前半になら。私たちは合計の長さをp以下にしました。したがって、中間点をp/2で "移動"しました。今は中間点がbで続きますが、単語はaで始まります。フォームww

同じ引数で、それが後半にあるために行きます。

ここでは、中間が含まれているとし、uwy（n=0を使用）を考えてみましょう。 |vwx|<=p以来、私たちは途中ではなく、Aさんとの縁のBさんからAさんとBさんから削除しました。また、正の量の文字を削除しましたので、uwyはk<pまたはm<pのいずれかの形式のa^p b^k a^m b^pです。 Eitherway、それはww

の形式ではありません