Estaba en una entrevista, y me pidieron que diera la cadena más corta generada dada esta gramática libre de contexto. No repasé en años, así que creo que me equivoqué. ¿Cuál es la respuesta para saberla para el futuro?
$$\begin{align*} &S\to ABA\mid SS\\ &A\to S0\mid T1T\\ &B\to S1\mid 0\\ &T\to 0 \end{align*}$$
Gracias.
Para obtener una cadena de terminales, debe deshacerse de los no terminales $S$ y $A$ . Utilizando $S\to SS$ claramente no ayuda, por lo que debe comenzar con $S\to ABA$ . La única manera de deshacerse del $A$ es con $A\to T1T$ Así que lo mejor que puedes hacer es $S\to ABA\to^* T1T0T1T\to^* 0100010$ .
En realidad, puede hacerlo a través de una forma de interpretación abstracta ¡! Vamos a interpretar esta gramática (no los árboles sintácticos, ¡la propia gramática!) en los naturales, es decir, la longitud mínima que puede generar cada no-terminal. Para ello, sustituiremos cada flecha de producción por '=', cada terminal por 1, la concatenación por '+' y la alternancia por 'min'. Para mayor claridad, escribiré los símbolos de la interpretación en minúsculas (y voy a pasar por encima de algunos detalles).
Aplicando este procedimiento a la gramática dada, obtenemos: $$\begin{align} &s = \min(a + b + a, s + s) \\ &a = \min(s + 1, t + 1 + t) \\ &b = \min(s+1,1) \\ &t = 1 \end{align} $$
Sustituyendo $t=1$ (es decir, hemos descubierto que $T$ produce al menos un terminal), y utilizando $\min(a+c,b+c)=\min(a,b)+c$ nos encontramos con que: $$\begin{align} &s = \min(a + b + a, s + s) \\ &a = \min(s, 2) + 1 \\ &b = \min(s,0) + 1 \end{align} $$
Ahora podemos deducir (utilizando $x \geq 0 \implies \min(x,0) = 0$ ) que $b = 1$ . Sustituyendo eso nos da: $$\begin{align} &s = \min(2a + 1, 2s) \\ &a = \min(s, 2) + 1 \end{align} $$
Ahora estamos aparentemente atascados, debido a la recursión mutua entre $a$ y $s$ . Y de hecho, $s=0, a=1$ sería una solución para este último sistema. Esto corresponde (vagamente) a la utilización de la producción $S \to SS$ para siempre, sin producir ninguna terminal. Pero también podríamos razonar que $S$ nunca puede producir la cadena vacía - haciendo una segunda interpretación, ¡que pondré al final para seguir con esta historia!
Así que también tenemos $s \geq 1$ . Al conectar esto a $s = \min(2a + 1, 2s)$ junto con $a \geq 1$ nos da $s \geq 2$ De ahí que $a \geq 3$ . De ello se desprende que $s \geq 4$ y finalmente llegamos a $s \geq 7$ .
Por lo tanto, tenemos que $s=7, a=3$ es una solución del último sistema de ecuaciones mostrado, sujeta a la restricción de que $s \geq 1$ . De ello se concluye finalmente que $S$ produce al menos 7 terminales.
Esto puede parecer un montón de trabajo para un problema tan trivial, pero después de la idea de utilizar una segunda interpretación, no requiere grandes saltos de conocimiento por lo que un ordenador podría hacerlo. De hecho, los generadores de analizadores sintácticos utilizan un procedimiento similar para ver cuál puede ser el primer terminal procedente de un no-terminal y así sucesivamente.
Uno de los detalles que he omitido es que una gramática simple como $S \to 1S$ (con interpretación $s = s+1$ aparentemente no tiene solución - pero la tiene, $s=\infty$ ¡! Hay formas de evitar esto, por supuesto (se podría demostrar que esta nueva gramática no termina mediante otra interpretación abstracta, o se podría interpretar en $\mathbb{N} \cup \{\infty\}$ pero espero haber captado al menos la idea básica...
En lugar de una interpretación numérica, vamos a interpretar la gramática en los booleanos, para responder a la pregunta "¿Puede este terminal producir la cadena vacía?" Un terminal es interpretado por false( $\perp$ ), la concatenación por $\wedge$ y la alternancia por $\vee$ (y la cadena vacía por la verdad, pero eso no es necesario aquí). Obtenemos:
$$\begin{align} &s = (a \wedge b \wedge a) \vee (s \wedge s) \\ &a = (s \wedge \perp) \vee (t \wedge \perp \wedge t) \\ &b = (s \wedge \perp) \vee \perp \\ &t = \perp \end{align} $$
Con un poco de lógica booleana, esto se simplifica rápidamente a $s,a,b,t=\perp$ por lo que ninguno de los no-terminales puede producir la cadena vacía. ¡Uf!
Dejemos que $m$ sea la longitud de la cadena más corta producida por $S$ . Estamos tratando de encontrar $m$ .
$T$ y $B$ claramente no puede convertirse en ninguna cadena de longitud inferior a 1.
$A$ puede convertirse en $S0$ o $T1T$ . $S0$ debe convertirse en una cadena de longitud al menos $m+1$ y por hipótesis podemos producir una cadena de longitud $m$ a partir de $S$ y $m+1$ no es el más corto. Así que si alguna vez usamos $A$ será a través del $T1T$ produciendo una cadena de al menos 3 caracteres.
$S$ puede convertirse en $SS$ que tiene una longitud mínima de $2m$ . Pero $2m \ge m$ por lo que debe haber una forma de producir la cadena más corta posible sin utilizar el $SS$ producción. Así que debe haber una manera de producirlo usando sólo el $ABA$ producción. Cualquier cadena producida por $ABA$ tiene una longitud mínima de $3 + 1 + 3 = 7$ .
Así que la respuesta es $S\to ABA \to T1T\ 0\ T1T \to 010\ 0\ 010$ para una longitud de 7.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
