Prouver la langue $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$ n'est pas sans contexte en utilisant le lemme de pompage
$\textit{Proof}$. Laisser$A$ être la langue $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$. Nous utiliserons le lemme de pompage pour prouver que$A$n'est pas un langage sans contexte (CFL). La preuve est par contradiction.
Supposer que $A$est CFL. Laisser$p$être la longueur de pompage donnée par le lemme de pompage. Laisser$s$ être la chaîne $1^{p}0^{p}0^{p}1^{p}$. Depuis$s \in A$ et $|s| \geq p$, le lemme de pompage garantit que $s$ peut être divisé en cinq morceaux, $𝑠=uvxyz$, satisfaisant les conditions suivantes:
- pour chaque $i \geq 0$, $uv^{i}xy^{i}z \in A$,
- $|vy| > 0$
- $|vxy| \leq p$
Ensuite, par condition 3, nous avons que $vxy$ est une sous-chaîne de la première moitié de $s\ (1^{p}0^{p})$, ou $vxy$ est une sous-chaîne du milieu de $s\ (0^{p}0^{p})$, ou $vxy$ est une sous-chaîne de la seconde moitié de $s\ (0^{p}1^{p})$. Analysons chaque cas:
- Si $vxy$ est une sous-chaîne de la première moitié de $s\ (1^{p}0^{p})$, puis, $vxy$ ne peut avoir que $1's$, ou peut avoir les deux $1's$ et $0's$, ou ne peut avoir que $0's$. Analysons chaque cas:
- Si $vxy$ contient seulement $1's$, puis, $uv^{0}xy^{0}z = uxz$ aura moins $1's$ que $0's$, Donc $uxz \notin A$, et puis la condition 1 é violée, nous avons donc une contradiction.
- Si $vxy$ contient $1's$ et $0's$, puis $uv^{0}xy^{0}z = uxz \neq (uxz)^{R}$, Donc $uxz \notin A$, et puis la condition 1 é violée, nous avons donc une contradiction.
- Si $vxy$ contient seulement $0's$, puis, $uv^{0}xy^{0}z = uxz$ aura moins $0's$ que $1's$, Donc $uxz \notin A$, et puis la condition 1 é violée, nous avons donc une contradiction.
- Si $vxy$ est une sous-chaîne du milieu de $s\ (0^{p}0^{p})$. Dans ce cas$vxy$ n'aura qu'une sorte de symbole, donc, $ uv^{0}xy^{0}z = uxz$ aura moins $0's$ que $1's$, Donc $uxz \notin A$, et puis la condition 1 é violée, nous avons donc une contradiction.
- Si $vxy$ est une sous-chaîne de la seconde moitié de $s\ (0^{p}1^{p})$, Donc, $vxy$ ne peut avoir que $0's$, ou peut avoir les deux $0's$ e $1's$, ou ne peut avoir que $1's$. Analysons chaque cas:
- Si $vxy$ ont seulement $0's$, puis, $uv^{0}xy^{0}z = uxz$ aura moins $0's$ que $1's$, Donc $uxz \notin A$, et puis la condition 1 é violée, nous avons donc une contradiction.
- Si $vxy$ avoir $0's$ et $1's$, puis, $uv^{0}xy^{0}z = uxz \neq (uxz)^{R}$, Donc $uxz \notin A$, et puis la condition 1 é violée, nous avons donc une contradiction.
- Si $vxy$ ont seulement $1's$, puis, $uv^{0}xy^{0}z = uxz$ aura moins $1's$ que $0's$, Donc $uxz \notin A$, et puis la condition 1 é violée, nous avons donc une contradiction.
Puisque nous avons analysé tous les cas possibles et que dans tous les cas une contradiction était inévitable, nous pouvons conclure que $A$ n'est pas CFL. $\square$
J'ai essayé de couvrir tous les cas possibles. Mais je ne suis pas sûr que ce soit correct ou si cela peut être simplifié davantage.
Réponses
C'est correct et clair, mais cela pourrait être simplifié. Il n'y a vraiment que deux cas.
- Si $vxy$ ne contient que des zéros ou des uns, le pompage dans les deux sens produira un mot $w$ tel que $|w|_0\ne|w|_1$.
- Si $vxy$ contient à la fois des zéros et des uns, puis il coupe un seul des deux blocs de uns dans $s$, et le pompage dans les deux sens produira un mot $w$ tel que $w\ne w^R$.