Udowodnienie języka $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$ nie jest wolne od kontekstu przy użyciu lematu pompowania

Nov 20 2020

$\textit{Proof}$. Pozwolić$A$ być językiem $\{w \in \{0, 1\}^{\ast} : w = w^{R}$, $|w|_{0} = |w|_{1} \}$. Aby to udowodnić, użyjemy lematu pompowania$A$nie jest językiem bezkontekstowym (CFL). Dowód jest sprzeczny.

Przypuszczam, że $A$jest CFL. Pozwolić$p$być długością pompowania określoną w lemacie pompowania. Pozwolić$s$ być ciągiem $1^{p}0^{p}0^{p}1^{p}$. Od$s \in A$ i $|s| \geq p$, Lemat pompowania gwarantuje to $s$ można podzielić na pięć części, $𝑠=uvxyz$spełniające następujące warunki:

  1. dla każdego $i \geq 0$, $uv^{i}xy^{i}z \in A$,
  2. $|vy| > 0$
  3. $|vxy| \leq p$

Następnie, zgodnie z warunkiem 3, mamy to $vxy$ jest podciągiem pierwszej połowy $s\ (1^{p}0^{p})$lub $vxy$ jest podciągiem ze środka $s\ (0^{p}0^{p})$lub $vxy$ jest podciągiem drugiej połowy programu $s\ (0^{p}1^{p})$. Przeanalizujmy każdy przypadek:

  1. Gdyby $vxy$ jest podciągiem pierwszej połowy $s\ (1^{p}0^{p})$, następnie, $vxy$ może mieć tylko $1's$lub może mieć oba $1's$ i $0's$lub może mieć tylko $0's$. Przeanalizujmy każdy przypadek:
    1. Gdyby $vxy$ zawiera tylko $1's$, następnie, $uv^{0}xy^{0}z = uxz$ będzie mniej $1's$ niż $0's$, więc $uxz \notin A$, a następnie warunek 1 é został naruszony, dlatego mamy sprzeczność.
    2. Gdyby $vxy$ zawiera $1's$ i $0's$, następnie $uv^{0}xy^{0}z = uxz \neq (uxz)^{R}$, więc $uxz \notin A$, a następnie warunek 1 é został naruszony, dlatego mamy sprzeczność.
    3. Gdyby $vxy$ zawiera tylko $0's$, następnie, $uv^{0}xy^{0}z = uxz$ będzie mniej $0's$ niż $1's$, więc $uxz \notin A$, a następnie warunek 1 é został naruszony, dlatego mamy sprzeczność.
  2. Gdyby $vxy$ jest podciągiem ze środka $s\ (0^{p}0^{p})$. W tym przypadku$vxy$ będzie miał tylko rodzaj symbolu, a zatem $ uv^{0}xy^{0}z = uxz$ będzie mniej $0's$ niż $1's$, więc $uxz \notin A$, a następnie warunek 1 é został naruszony, dlatego mamy sprzeczność.
  3. Gdyby $vxy$ jest podciągiem drugiej połowy programu $s\ (0^{p}1^{p})$więc $vxy$ może mieć tylko $0's$lub może mieć oba $0's$ mi $1's$lub może mieć tylko $1's$. Przeanalizujmy każdy przypadek:
    1. Gdyby $vxy$ mam tylko $0's$, następnie, $uv^{0}xy^{0}z = uxz$ będzie mniej $0's$ niż $1's$, więc $uxz \notin A$, a następnie warunek 1 é został naruszony, dlatego mamy sprzeczność.
    2. Gdyby $vxy$ mieć $0's$ i $1's$, następnie, $uv^{0}xy^{0}z = uxz \neq (uxz)^{R}$, więc $uxz \notin A$, a następnie warunek 1 é został naruszony, dlatego mamy sprzeczność.
    3. Gdyby $vxy$ mam tylko $1's$, następnie, $uv^{0}xy^{0}z = uxz$ będzie mniej $1's$ niż $0's$, więc $uxz \notin A$, a następnie warunek 1 é został naruszony, dlatego mamy sprzeczność.

Ponieważ przeanalizowaliśmy wszystkie możliwe przypadki i we wszystkich przypadkach sprzeczność była nieunikniona, możemy to stwierdzić $A$ nie jest CFL. $\square$

Starałem się objąć wszystkie możliwe przypadki. Ale nie jestem pewien, czy to prawda, czy można to jeszcze bardziej uprościć.

Odpowiedzi

1 BrianM.Scott Nov 24 2020 at 22:57

Jest poprawny i jasny, ale można go uprościć. Tak naprawdę są tylko dwa przypadki.

  • Gdyby $vxy$ zawiera tylko zera lub tylko jedynki, pompowanie w dowolnym kierunku wygeneruje słowo $w$ takie że $|w|_0\ne|w|_1$.
  • Gdyby $vxy$ zawiera zarówno zera, jak i jedynki, przecina tylko jeden z dwóch bloków jedynek w $s$, a pompowanie w dowolnym kierunku da słowo $w$ takie że $w\ne w^R$.