Prueba de corrección de gramática

Question

Estoy teniendo dificultades en la demostración de la corrección de las gramáticas. El siguiente problema y mi pena intentar resolver es mostrar que no puedo entender incluso los fundamentos de tales pruebas. Muy frutstrating....

Podría alguien que me señale en la dirección correcta?

El libro de texto utilizado en mi clase de "Introducción a la Teoría de Autómatas, Lenguajes y Computación (2ª Edición) por Juan Hopcroft". Contiene una breve descripción de cómo manejar estas pruebas en la página 179, en el cuadro de "La Forma de las Pruebas Sobre las Gramáticas". Él utiliza un lenguaje de palíndromos como ejemplo, que es mucho más fácil que el siguiente problema (en mi humilde opinión).

Hay algún lugar donde puedo encontrar ejemplos de la gramática de las pruebas?

Gracias! .. y aquí está el problema:

"Vamos a L ser el idioma en el ({a,b}), de todas las cadenas con un número igual de 'a' y 'b'.

$S \to \epsilon | aB | bA$
$A \to aS | bAA$
$B \to bS | aBB$

Demostrar que G genera lenguaje L. "

$\forall w, G\overset{*}{\Rightarrow }w \Leftrightarrow |w|_a=|w|_b$

Demostrando el lado izquierdo por inducción sobre el número de derivación pasos y el lado derecho de la longitud de w Base: Lado izquierdo (una derivación de paso):
$G\overset{*}{\Rightarrow }\epsilon$
$|\epsilon |_a=|\epsilon |_b$

Lado derecho (longitud de w es 0):

$|\epsilon |_a=|\epsilon |_b$
$G\overset{*}{\Rightarrow }\epsilon$

Inducción: Lado derecho (longitud de w es n+1)

w=sa (es un símbolo y |s|=n)
$|s|_a=|s|_b$ (hipótesis inductiva)
$G\overset{*}{\Rightarrow}s\overset{*}{\Rightarrow }sa$

Yo no puedo ir hormiga más... :(

Answer 1

Usted tiene que demostrar dos cosas:

1. Para cada una de las $w\in\{a,b\}^*$ si $G\stackrel{*}\Rightarrow w$,$|w|_a=|w|_b$.

2. 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?

Answer 2

Para mostrar que cada palabra que puede ser producido por la gramática $G$ contiene un número igual de 'a' y 'b' demostrar por inducción que en cada paso el número de "a", más el número de 'A' es igual al número de la " b " más el número de 'B'. Tenga en cuenta que la palabra inicial, $S$ tiene esta propiedad y que es conservado por cualquiera de las reglas de producción. Ya que la palabra no puede contener el los símbolos no terminales de la 'a' y 'B' debe contener un número igual de 'a' y 'b'.

Para el reverso de la inclusión, vamos a $w$ ser una palabra que contiene un número igual de 'a' y 'b' y el uso de la inducción por la longitud de la palabra para mostrar que $w$ puede ser producido por $G$. Si $w$ es la palabra vacía, sólo tiene que utilizar la regla de $S \rightarrow \varepsilon$. De lo contrario, $w$ debe contener $ab$ o $ba$ como una subcadena, w.l.o.g. deje $w = uabv$ palabras $u$$v$. A continuación, $uv$ contiene un número igual de 'a' y 'b', por lo que puede ser producido en $G$ por la hipótesis de inducción. En la izquierda de la derivación de $uv$, debe haber algo intermedio palabra $uXy$ donde $X$ es un símbolo no terminal, es decir,$X \in \{S,A,B\}$. Por las reglas dadas, es posible deducir $abX$ $X$ (por ejemplo,$A \Rightarrow aS \Rightarrow abA$, igualmente para$B$$S$). Así que usted puede derivarse $uabXy$$G$. A continuación, como en la derivación de $uv$ para obtener una derivación de $w = uabv$.