¿Es mi ejemplo suficiente para la pregunta a continuación, CFG, Por favor ayuda

Question

¿Es mi ejemplo suficiente para la siguiente pregunta?

$Pregunta:$

Proporcione un contraejemplo para mostrar que la siguiente construcción no logra demostrar que la clase de lenguajes libre de contexto es cerrada bajo estrella. Sea $A$ un $LFC$ generado por el $GCL$ $G = (V, \sum, R, S)$. Agregue la nueva regla $S \Rightarrow SS$ y llame a la gramática resultante $G'$. Se supone que esta gramática genera $A$*.

$Mi\ Ejemplo:$

Supongamos el lenguaje libre de contexto A, y la gramática correspondiente es $G = \{\{S\} , \{( , )\} , \{S\Rightarrow (S), S \Rightarrow \epsilon\}, S\}$. Entonces, si agregamos $S \Rightarrow SS$ y obtenemos la nueva gramática $G'$, el lenguaje generado por $G'$ tendrá $(()())$, que no está contenido en $A$*. Por lo tanto, la nueva gramática no genera $A$* en este caso.

Answer 1

Su ejemplo está bien. Sin embargo, agregaría una pequeña explicación de por qué $(()())$ no está en $A^*$, para demostrar que comprendes y no estás fingiendo. Pero de hecho, tu solución demuestra que el problema es que $S \to SS$ solo se debe aplicar en el nivel superior y no "más profundo" dentro de las derivaciones. Por lo general, esto se hace cumplir teniendo un nuevo axioma.

Pequeña nota. Estoy acostumbrado a escribir $\to$ para reglas (=producciones) y $\Rightarrow$ para pasos de derivación.

Answer 2

Tu ejemplo es correcto.

Para asegurarte de que estás produciendo A*, deberías agregar un nuevo símbolo de inicio, digamos X y agregar las reglas:

X → XS | épsilon

Answer 3

Dado que A* debe contener la cadena vacía, si A no tiene la cadena vacía (la derivación "S-> ϵ" no está en el conjunto de producciones de la gramática que genera A), entonces la derivación "S->SS" no generará ninguna cadena vacía, aunque A* debe tener ϵ -><-