Jak można ws z | w | = | s | a my będziemy bez kontekstu, podczas gdy w # s nie jest?

Dlaczego (jeśli tak) separator $\#$ robi różnicę między tymi dwoma językami?

Powiedzmy:

$L=\{ws : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \}$

$L_{\#}=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \}$

Oto dowód i gramatyk reprezentujący$L$ jak $CFL$

A poniżej dodam dowód na to $L_{\#} \notin CFL$ :

Czy $\#$znak naprawdę robi różnicę? jeśli tak, to dlaczego? a jeśli nie, to który z dowodów jest błędny i gdzie?

Udowodnij to $L_{\#} \notin CFL$ :

Załóżmy w drodze sprzeczności, że $L ∈ CFL$. Pozwolić$p > 0$ być stałą pompowania dla $L$ gwarantowane przez pompujący lemat dla języków bezkontekstowych. Rozważamy to słowo $s = 0^{m}1^{p}\#0^{p}1^{m}$ gdzie $m=p!+p$ więc $s ∈ L$. Od$|s| > p$, zgodnie z lematem pompowania istnieje reprezentacja $s = uvxyz$, takie że $|vy| > 0$, $|vxy| ≤ p$ , i $uv^{j}xy^{j} z ∈ L$ dla każdego $j ≥ 0$.

Spotyka się sprzeczność w przypadkach:

• Gdyby $v$ lub $y$ zawierać $\#$: Więc dla $i = 0$rozumiemy $uxz$ nie zawiera $\#$, więc $uxz \notin L$ w przeciwieństwie.

• Jeśli oba $v$ i $y$ są pozostawione $\#$: Więc dla $i = 0$rozumiemy $uxz$ ma formę $w\#x$, gdzie $|w| < |x|$, więc $uxz \notin L$.

• Jeśli oba $v$ i $y$ mają rację $\#$: Podobny do ostatniego przypadku.

• Gdyby $v$ pozostaje do $\#$, $y$ ma rację i $|v| < |y|$: Więc dla $i = 0$rozumiemy $uxz$ ma formę $w\#x$, gdzie $|w| > |x|$, więc $uxz \notin L$.

• Gdyby $v$ pozostaje do $\#$, $y$ ma rację i $|v| > |y|$: Podobny do ostatniego przypadku.

• Gdyby $v$ pozostaje do $\#$, $y$ ma rację i $|v| = |y|$: To najciekawszy przypadek. Od$|vxy| ≤ p$, $v$ muszą być zawarte w $1^{p}$ część $s$, i $y$ w $0^{p}$część. Tak to utrzymuje$v = 1^{k}$ i $y = 0^{k}$ za to samo $1 ≤ k ≤ p$ (w rzeczywistości musi tak być $k < p/2$). Dla każdego$j ≥ 0$, trzyma to $uv^{j+1}xy^{j+1}z = 0^{m}1^{p+j·k}\#0^{p+j·k}1^{m}$, więc jeśli tak się stanie $m = p + j · k$, to trzyma to $uv^{j+1}xy^{j+1}z \notin L$w przeciwieństwie. Aby to osiągnąć, musimy wziąć$j = (m-p)/k$, który jest ważny tylko wtedy, gdy $m − p$ jest podzielny przez $k$. Przypomnijmy, że wybraliśmy$m = p + p!$, więc $m − p = p!$, i $p!$ jest podzielny przez kogokolwiek $1 ≤ k ≤ p$ jak chciałem.

Twój dowód jest poprawny, a myliłem się. Zajęło mi trochę czasu, aby ustalić, gdzie było moje zamieszanie, ale z pomocą Yuvala chyba to zrozumiałem.

Rozważmy trzy języki

$\qquad\begin{align*} &L_= &\!\!\!\!\!\!\!\!\! &= \{ xy \mid |x| = |y|, x \neq y \}, \\ &L_{\#} &\!\!\!\!\!\!\!\!\! &= \{ x\#y \mid x \neq y \},\ \text{and} \\ &L_{=\#} &\!\!\!\!\!\!\!\!\! &= \{ x\#y \mid |x| = |y|, x \neq y \}. \end{align*}$

Jak widzieliśmy tutaj ,$L_=$jest bezkontekstowy. W gramatyce polega na tym, aby generować symbole „po prawej”, ale policzyć je „po lewej” później (lub na odwrót), upewniając się, że niedopasowane symbole pojawiają się w pasujących pozycjach. Warunek długości jest trywialny, ponieważ zmniejsza się do równej długości.
Możesz zbudować NPDA z podobnym pomysłem, używając stosu, aby dopasować pozycję.

$L_\#$ jest również pozbawiony kontekstu . Dowód jest jeszcze prostszy: niedopasowane symbole pojawiają się w tej samej odległości od początku wzgl. separator. Nierówne długości można sprawdzić osobno; niedeterminizm „wybiera” między dwiema opcjami.

Teraz, jak pokazujesz, $L_{=\#}$nie jest kontekstowe. Oto dlaczego dowody na pozostałe dwa języki się psują.

1. W gramatyce dla $L_=$, jeśli musimy wygenerować separator pośrodku, nie możemy „ponownie przypisać” symboli z „lewej” na „prawą”.
2. Zamiast „zaakceptuj, jeśli długości są nierówne lub niezgodne”, musimy „zaakceptować, jeśli długości są równe i niezgodne”. Niedeterminizm nie może nam pomóc z i !

Sprowadza się więc intuicyjnie do warunków formy „$x \neq y$" i "$|x| = |y|$„oba są„ bezkontekstowe ”w tym sensie, że można je sprawdzić za pomocą stosu, ale nie przy użyciu kontroli skończonej. Dlatego PDA może wykonać jedno, ale nie jedno i drugie.

PDA dla $L_=$„kody”, ponieważ tak naprawdę nie sprawdzają tych warunków$x$ i $y$; dzieli słowo w inny sposób. To już nie jest możliwe, jeśli masz separator.

Uzupełnienie: I śmiało twierdził, że$L_= \in \mathrm{CFL} \implies L_{=\#} \in \mathrm{CFL}$ponieważ CFL jest zamknięty przeciwko odwrotnemu homomorfizmowi. Chociaż to prawda$f(L_{=\#}) = L_=$ z $f$ tożsamość oprócz tego, że jest usuwana $\#$, to nie ma znaczenia. $f^{-1}(L_=) = L_\#$; nic nie można powiedzieć$L_{=\#}$.

Dodatek II: Uwaga :$L = \{ x\#y \mid |x| = |y| \}$jest trywialnie pozbawiony kontekstu. Dlatego z$L \cap L_\# = L_{=\#}$ mamy dobry przykład na to, że CFL nie jest zamknięty przed skrzyżowaniem.