Die Sprache beweisen $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$ ist mit Pumping Lemma nicht kontextfrei

Question

$\textit{Proof}$. Lassen$A$ sei die Sprache $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$. Wir werden das Pumping Lemma verwenden, um dies zu beweisen$A$ist keine kontextfreie Sprache (CFL). Der Beweis ist im Widerspruch.

Nehme an, dass $A$ist CFL. Lassen$p$sei die vom Pump-Lemma angegebene Pumplänge. Lassen$s$ sei die Zeichenfolge $1^{p}0^{p}0^{p}1^{p}$. Schon seit$s \in A$ und $|s| \geq p$Das garantiert das Pumping Lemma $s$ kann in fünf Teile geteilt werden, $𝑠=uvxyz$, die folgenden Bedingungen erfüllen:

1. für jeden $i \geq 0$, $uv^{i}xy^{i}z \in A$,
2. $|vy| > 0$
3. $|vxy| \leq p$

Dann haben wir unter Bedingung 3 das $vxy$ ist ein Teilstring der ersten Hälfte von $s\ (1^{p}0^{p})$, oder $vxy$ ist ein Teilstring der Mitte von $s\ (0^{p}0^{p})$, oder $vxy$ ist ein Teilstring der zweiten Hälfte von $s\ (0^{p}1^{p})$. Lassen Sie uns jeden Fall analysieren:

1. Wenn $vxy$ ist ein Teilstring der ersten Hälfte von $s\ (1^{p}0^{p})$, dann, $vxy$ kann nur haben $1's$oder kann beides haben $1's$ und $0's$oder kann nur haben $0's$. Lassen Sie uns jeden Fall analysieren:
1. Wenn $vxy$ enthält nur $1's$, dann, $uv^{0}xy^{0}z = uxz$ wird weniger haben $1's$ als $0's$also $uxz \notin A$und dann wurde die Bedingung 1 verletzt, daher haben wir einen Widerspruch.
2. Wenn $vxy$ enthält $1's$ und $0's$, dann $uv^{0}xy^{0}z = uxz \neq (uxz)^{R}$also $uxz \notin A$und dann wurde die Bedingung 1 verletzt, daher haben wir einen Widerspruch.
3. Wenn $vxy$ enthält nur $0's$, dann, $uv^{0}xy^{0}z = uxz$ wird weniger haben $0's$ als $1's$also $uxz \notin A$und dann wurde die Bedingung 1 verletzt, daher haben wir einen Widerspruch.
2. Wenn $vxy$ ist ein Teilstring der Mitte von $s\ (0^{p}0^{p})$. In diesem Fall$vxy$ wird also nur eine Art Symbol haben, also $ uv^{0}xy^{0}z = uxz$ wird weniger haben $0's$ als $1's$also $uxz \notin A$und dann wurde die Bedingung 1 verletzt, daher haben wir einen Widerspruch.
3. Wenn $vxy$ ist ein Teilstring der zweiten Hälfte von $s\ (0^{p}1^{p})$also $vxy$ kann nur haben $0's$oder kann beides haben $0's$ e $1's$oder kann nur haben $1's$. Lassen Sie uns jeden Fall analysieren:
1. Wenn $vxy$ habe nur $0's$, dann, $uv^{0}xy^{0}z = uxz$ wird weniger haben $0's$ als $1's$also $uxz \notin A$und dann wurde die Bedingung 1 verletzt, daher haben wir einen Widerspruch.
2. Wenn $vxy$ haben $0's$ und $1's$, dann, $uv^{0}xy^{0}z = uxz \neq (uxz)^{R}$also $uxz \notin A$und dann wurde die Bedingung 1 verletzt, daher haben wir einen Widerspruch.
3. Wenn $vxy$ habe nur $1's$, dann, $uv^{0}xy^{0}z = uxz$ wird weniger haben $1's$ als $0's$also $uxz \notin A$und dann wurde die Bedingung 1 verletzt, daher haben wir einen Widerspruch.

Da wir alle möglichen Fälle analysiert haben und in allen Fällen ein Widerspruch unvermeidlich war, können wir daraus schließen $A$ ist nicht CFL. $\square$

Ich habe versucht, alle möglichen Fälle abzudecken. Ich bin mir aber nicht sicher, ob dies richtig ist oder ob es weiter vereinfacht werden kann.

Answer 1

Es ist richtig und klar, aber es könnte vereinfacht werden. Es gibt wirklich nur zwei Fälle.

• Wenn $vxy$ Enthält nur Nullen oder nur Einsen. Wenn Sie in eine der beiden Richtungen pumpen, wird ein Wort erzeugt $w$ so dass $|w|_0\ne|w|_1$.
• Wenn $vxy$ enthält sowohl Nullen als auch Einsen, dann schneidet es nur einen der beiden Einsenblöcke in $s$Wenn Sie in eine der beiden Richtungen pumpen, wird ein Wort erzeugt $w$ so dass $w\ne w^R$.