言語を証明する $\{w \in \{0, 1\}^{\ast} : w = w^{R}$、 $|w|_{0} = |w|_{1} \}$ ポンピング補題を使用した文脈自由ではありません

Nov 20 2020

$\textit{Proof}$。しましょう$A$ 言語になる $\{w \in \{0, 1\}^{\ast} : w = w^{R}$、 $|w|_{0} = |w|_{1} \}$。ポンピング補題を使用して、$A$文脈自由言語（CFL）ではありません。その証拠は矛盾によるものです。

仮定 $A$CFLです。しましょう$p$ポンピング補題によって与えられるポンピング長さである。しましょう$s$ 文字列になります $1^{p}0^{p}0^{p}1^{p}$。以来$s \in A$ そして $|s| \geq p$、PumpingLemmaはそれを保証します $s$ 5つの部分に分けることができます、 $𝑠=uvxyz$、次の条件を満たす：

それぞれについて $i \geq 0$、 $uv^{i}xy^{i}z \in A$、
$|vy| > 0$
$|vxy| \leq p$

次に、条件3により、次のようになります。 $vxy$ の前半の部分文字列です $s\ (1^{p}0^{p})$、または $vxy$ の真ん中の部分文字列です $s\ (0^{p}0^{p})$、または $vxy$ の後半の部分文字列です $s\ (0^{p}1^{p})$。それぞれのケースを分析してみましょう。

場合 $vxy$ の前半の部分文字列です $s\ (1^{p}0^{p})$、その後、 $vxy$ しか持てない $1's$、または両方を持つことができます $1's$ そして $0's$、または $0's$。それぞれのケースを分析してみましょう。

場合 $vxy$ のみが含まれています $1's$、その後、 $uv^{0}xy^{0}z = uxz$ 少なくなります $1's$ より $0's$、したがって $uxz \notin A$、そして条件1éに違反したため、矛盾が生じます。
場合 $vxy$ 含まれています $1's$ そして $0's$、その後 $uv^{0}xy^{0}z = uxz \neq (uxz)^{R}$、したがって $uxz \notin A$、そして条件1éに違反したため、矛盾が生じます。
場合 $vxy$ のみが含まれています $0's$、その後、 $uv^{0}xy^{0}z = uxz$ 少なくなります $0's$ より $1's$、したがって $uxz \notin A$、そして条件1éに違反したため、矛盾が生じます。

場合 $vxy$ の真ん中の部分文字列です $s\ (0^{p}0^{p})$。この場合$vxy$ したがって、一種の記号しかありません。 $ uv^{0}xy^{0}z = uxz$ 少なくなります $0's$ より $1's$、したがって $uxz \notin A$、そして条件1éに違反したため、矛盾が生じます。
場合 $vxy$ の後半の部分文字列です $s\ (0^{p}1^{p})$したがって、 $vxy$ しか持てない $0's$、または両方を持つことができます $0's$ e $1's$、または $1's$。それぞれのケースを分析してみましょう。

場合 $vxy$ 持っているだけ $0's$、その後、 $uv^{0}xy^{0}z = uxz$ 少なくなります $0's$ より $1's$、したがって $uxz \notin A$、そして条件1éに違反したため、矛盾が生じます。
場合 $vxy$ 持ってる $0's$ そして $1's$、その後、 $uv^{0}xy^{0}z = uxz \neq (uxz)^{R}$、したがって $uxz \notin A$、そして条件1éに違反したため、矛盾が生じます。
場合 $vxy$ 持っているだけ $1's$、その後、 $uv^{0}xy^{0}z = uxz$ 少なくなります $1's$ より $0's$、したがって $uxz \notin A$、そして条件1éに違反したため、矛盾が生じます。

考えられるすべてのケースを分析し、すべてのケースで矛盾が避けられなかったので、次のように結論付けることができます。 $A$ CFLではありません。 $\square$

私は考えられるすべてのケースをカバーしようとしました。しかし、これが正しいかどうか、またはさらに単純化できるかどうかはわかりません。

言語を証明する $\{w \in \{0, 1\}^{\ast} : w = w^{R}$、 $|w|_{0} = |w|_{1} \}$ ポンピング補題を使用した文脈自由ではありません

回答