Usted tiene que demostrar dos cosas:
Para cada una de las $w\in\{a,b\}^*$ si $G\stackrel{*}\Rightarrow w$,$|w|_a=|w|_b$.
Para cada una de las $w\in\{a,b\}^*$ si $|w|_a=|w|_b$,$G\stackrel{*}\Rightarrow w$.
A veces una prueba por inducción es más fácil si usted probar algo más fuerte que el resultado deseado. Yo probaría (1) en la prueba de los siguientes más fuerte
Reclamo: Para $u\in\{S,A,B,a,b\}^*$ deje $\alpha(u)=|u|_a+|u|_A$$\beta(u)=|u|_b+|u|_B$. Vamos $$S=u_0 \Rightarrow u_1\Rightarrow u_2\Rightarrow\dots\Rightarrow u_n$$ be a derivation in $G$, where $u_k\in\{S,A,B,a,b\}^*$ for $k=0,\dots,n$. Then $\alpha(u_k)=\beta(u_k)$ for $k=0,\dots,n$. In particular, if $u_n\in\{a,b\}^*$, then $|w|_A=|w|_B=0$, so $$|u_n|_a=\alpha(u_n)=\beta(u_n)=|u_n|_b\;,$$ and therefore $u_n\en L$.
Me gustaría probar esto por inducción en $n$, la longitud de la derivación. La única derivación de longitud $1$ es la que ya tiene, $S\Rightarrow\epsilon$, e $\alpha(S)=\beta(S)=\alpha(\epsilon)=\beta(\epsilon)=0$, por lo que tenemos la inducción comenzó bien. Ahora supongamos que la Afirmación es verdadera para todas las derivaciones de longitud en la mayoría de las $n$, y vamos a $$S=u_0 \Rightarrow u_1\Rightarrow u_2\Rightarrow\dots\Rightarrow u_n\Rightarrow u_{n+1}$$ be a derivation of length $n+1$. Then $S=u_0 \Rightarrow u_1\Rightarrow u_2\Rightarrow\dots\Rightarrow u_n$ is a derivation of length $n$, so by the induction hypothesis $\alpha(u_k)=\beta(u_k)$ for $k=0,\dots,n$. To complete the induction step you must show that $\alpha(u_{n+1})=\beta(u_{n+1})$. You do this by investigating how each of the productions of $G$ changes $\alpha(u_n)$ and $\beta(u_n)$. Suppose, for instance, that the derivation $u_n\Rightarrow u_{n+1}$ uses the production $\a bAA$. Then $|u_{n+1}|_a=|u_n|_a$, $|u_{n+1}|_A=|u_n|A+1$, $|u_{n+1}|_b=|u_n|_b+1$, and $|u_{n+1}|_B=|u_n|_B$, so $\alpha(u_{n+1})=\alpha(u_n)+1=\beta(u_n)+1=\beta(u_{n+1})$, como se desee. Voy a dejar las otras seis producciones.
Añadido: La prueba de (2) es por inducción sobre la longitud de $w$, que por supuesto debe ser, incluso si $|w|_a=|w|_b$. Tienes esto empezó bien: si $|w|=0$,$w=\epsilon$, e $G\stackrel{*}\Rightarrow\epsilon$.
Supongamos ahora que si $|w|<2n$$|w|_a=|w|_b$,$G\stackrel{*}\Rightarrow w$; esa es su hipótesis de inducción. Deje $w\in\{a,b\}$ ser tal que $|w|=2n$$|w|_a=|w|_b=n$; usted necesita para demostrar que $G\stackrel{*}\Rightarrow w$.
Hay dos casos. El más simple es cuando se $w$ es la concatenación de dos cortas palabras pertenecientes a $L$; en ese caso, simplemente podemos "pegar" las derivaciones de la corta de palabras. He aquí una manera de hacer que precisa.
Deje $w=s_1s_2\dots s_{2n}$, donde cada una de las $s_k\in\{a,b\}$. Para $k=1,\dots,2n$ vamos $$m(k)=|s_1\dots s_k|_a-|s_1\dots s_k|_b\;,$$ the excess of $un$'s over $b$'s in the first $k$ letters of $w$. Suppose that $m(k)=0$ for some $k<2n$; then $k$ is even, and the words $u=s_1\dots s_k$ and $v=s_{k+1}\dots s_{2n}$ belong to $L$. (Why?) By the induction hypothesis, therefore, there are derivations $$S=u_0 \Rightarrow u_1\Rightarrow \dots\Rightarrow u_{p-1}\Rightarrow u_p=u\tag{1}$$ and $$S=v_0 \Rightarrow v_1\Rightarrow\dots\Rightarrow v_{q-1}\Rightarrow v_q=v\;.\tag{2}$$ The only terminal production is $S\to\epsilon$, so it must be the case that $u_{p-1}=xSy$, where $x,y\in\{a,b\}^*$ are such that $xy=u$. If $x=u$ and $y=\epsilon$, we can simply paste $(1)$ and $(2)$ together: $$S=u_0 \Rightarrow u_1\Rightarrow \dots\Rightarrow u_{p-1}=uS=uv_0\Rightarrow uv_1\Rightarrow\dots\Rightarrow uv_{q-1}\Rightarrow uv_q=uv=w\;,$$ and therefore $G\stackrel{*}\Rightarrow w$, como se desee.
Si $y\ne\epsilon$, me afirmación de que la derivación de $w$ puede ser reorganizado de modo que $u_{p-1}=uS$, y, a continuación, podemos pegar el reordenado derivación junto con $(2)$ a ver que $G\stackrel{*}\Rightarrow w$. Cada producción con la excepción de $S\to\epsilon$ deja un símbolo no terminal en la mano derecha final de la palabra, así que debe haber algo de $k<p$ tal que $u_k=xS$ $u_{k+1}=x$ algunos $x\in\{S,A,B,a,b\}^*$. A continuación, $x=u_{k+1}\stackrel{*}\Rightarrow w$ es un legítimo derivación en $G$, lo $S\stackrel{*}\Rightarrow xS\stackrel{*}\Rightarrow wS\Rightarrow w$ es un legítimo derivación de $w$ cuyo último paso nos permite pegarlo junto con el $(2)$.
Tenga en cuenta que $m(k)$ $m(k+1)$ siempre difieren en exactamente $1$, por lo que si $m(k)$ nunca cambia de signo como $k$ pistas de$1$$2n$, debe haber alguna $k<2n$ tal que $m(k)=0$. Ahora supongamos que $w$ no es la concatenación de dos cortas palabras de $L$; lo que significa que $m(k)\ne 0$$1\le k<2n$, lo $m(k)$ no cambia de signo $k$ pistas de$1$$2n$. Si $s_1=a$,$m(1)=1$, e $m(k)>0$$1\le k<2n$: cada apropiado segmento inicial de $w$ $a$'s de $b$'s. Pero sabemos que $m(2n)=0$, ya que el $w\in L$, por lo que debe ser el caso de que $m(2n-1)=1$, e $s_{2n}=b$. Del mismo modo, si $s_1=b$, luego $m(1)=-1$, $m(k)<0$ para $1\le k<2n$, cada apropiado segmento inicial de $w$ $b$'s de $a$'s, y $s_{2n}=a$.
En el primer caso $w=aub$ algunos $u\in\{a,b\}^*$, y en el segundo caso $w=bua$; en cualquier caso, es claro que $u\in L$. (Por qué?) Por otra parte, $|u|<2n$, de modo que por la hipótesis de inducción $G\stackrel{*}\Rightarrow u$. Se puede ver cómo modificar la derivación de $u$ para obtener una derivación de $w$, y de esta manera completar la inducción paso?
