Encontrar un valor apropiado para contradecir el lema de bombeo.

Question

Intento demostrar que $L=$ { $a^mb^n | n=m^2$ } no es un CFL con la ayuda del lema de bombeo para CFL's.

Elegí $w=a^mb^{m^2}$ = $a^{m-S}a^Sb^Tb^{m^2-T}$ $\in L$

Y ahora para contradecir el supuesto del lema de bombeo busco $i$ tal que $a^{m-S}a^{S^i}b^{T^i}b^{m^2-T}$ $\notin L$ para $i>=0$ .

¿Es posible encontrar dicho valor de $i$ ? ¿Cómo puedo demostrar que $b^{m^2-T+Ti}\neq b^{(m+1)^2}$ o $a^{m-S+Si}\neq a^{m+1}$ ?

Answer 1

No estás utilizando el lema de bombeo correctamente: no has mencionado la longitud de bombeo, no se te permite especificar un desglose concreto de $w$ en cinco (no cuatro) trozos, y sólo hay que demostrar que hay al menos un $i\ge 0$ tal que $uv^ixy^iz\notin L$ (donde $w=uvxyz$ con las restricciones adecuadas). Voy a hacer la mayor parte de un argumento correcto y dejar sólo la última parte para usted.

Supongamos que $L$ es un CFL, y sea $p$ sea un número de bombeo para $L$ . Sea $w=a^pb^{p^2}$ . Por el lema de bombeo podemos descomponer $w$ como $uvxyz$ para que $|vxy|\le p$ , $|vy|\ge 1$ y $uv^ixy^iz\in L$ para todos $i\ge 0$ . Hay que tener en cuenta tres casos:

1. $vxy=a^n$ para algún positivo $n\le p$ .
2. $vxy=a^mb^n$ para algún positivo $m$ y $n$ tal que $m+n\le p$ .
3. $vxy=b^n$ para algún positivo $n\le p$ .

En los casos (1) y (3) no debería tener problemas para ver que si $i\ne 1$ entonces $uv^ixy^iz\notin L$ sólo el caso (2) requiere un trabajo real.

Supongamos, entonces, que $vxy=a^mb^n$ para algún positivo $m$ y $n$ tal que $m+n\le p$ . Si $v$ contiene un $b$ es fácil ver que $uv^ixy^iz\notin L$ cuando $i>1$ ya que $v$ contiene $ba$ . Del mismo modo, $y$ no puede contener un $a$ . Por lo tanto, hay $r,s\ge 0$ tal que $v=a^r$ , $y=b^s$ y $r+s\ge 1$ por supuesto $x=a^{m-r}b^{n-s}$ . Entonces para $i\ge 0$ tenemos $$uv^ixy^iz=\underbrace{a^{p-m}}_u\underbrace{a^{ir}}_{v^i}\underbrace{a^{m-r}b^{n-s}}_x\underbrace{b^{is}}_{y^i}\underbrace{b^{p^2-n}}_z\;,$$ que se encuentra en $L$ si

$$(p-m+ir+m-r)^2=n-s+is+p^2-n\;,$$ es decir, si

$$\big(p+(i-1)r\big)^2=p^2+(i-1)s\;.$$

Sea $k=i-1$ y multiplicar y simplificar para obtener $2kpr+k^2r^2=ks$ . Así, o bien $k=0$ o $2pr+kr^2=s$ . Utilícelo para demostrar que existe como máximo un valor de $i$ diferente de $1$ tal que $uv^ixy^iz\in L$ y concluye que $L$ no es libre de contexto; conviene recordar que $r$ y $s$ no son a la vez $0$ .