[Jambo]

Buenos días, podrian ayudarme con el siguiente ejercicio?

Me piden construir una gramática para el lenguaje \[ L =\left\{{a^nb^k: k= 2^n \wedge n\geq{0}}\right\}  \] y esto fue lo que se me ocurrió:

\( S \rightarrow{IA | b} \)
\( A\rightarrow{aMA|aM} \)
\( aM\rightarrow{Mabb} \)
\( abbM\rightarrow{Mabb} \)
\( ba\rightarrow{ab} \)
\( IM\rightarrow{I} \)
\( I\rightarrow{\epsilon} \)

Me quedó diferente a la solución que me proponen, pero queria saber si mi razonamiento era correcto...

Agradezco su ayuda de antemano.

Saludos!

[manooooh]

Hola

Me piden construir una gramática para el lenguaje \[ L =\left\{{a^nb^k: k= 2^n \wedge n\geq{0}}\right\}  \] y esto fue lo que se me ocurrió:

\( S \rightarrow{IA | b} \)
\( A\rightarrow{aMA|aM} \)
\( aM\rightarrow{Mabb} \)
\( abbM\rightarrow{Mabb} \)
\( ba\rightarrow{ab} \)
\( IM\rightarrow{I} \)
\( I\rightarrow{\epsilon} \)

Me quedó diferente a la solución que me proponen, pero queria saber si mi razonamiento era correcto...

En lo marcado en rojo tienes una "producción" donde el lado izquierdo sólo tiene terminales; obligatoriamente debe haber al menos un noterminal, por lo que no está bien esa gramática.

Mira por aquí, dan varias alternativas para \( a^{2^n},\,n\geq0 \): https://cs.stackexchange.com/questions/76310/context-sensitive-grammar-for-a2n-mid-n-geq-0

Saludos

[Jambo]

Buenas, gracias por responder.

las gramaticas irrestrictas no permiten el uso de ese tipo de producciones? Tenia entendido que podian ser de la forma \( a\rightarrow{b} \) con \[ a \] y \[ b \] pertenecientes a \[ (V\cup{T}\cup{ϵ}) \] y \[ a\neq ϵ \] (donde \[ V \] variables y \[ T \] terminales)

[manooooh]

Hola

las gramaticas irrestrictas no permiten el uso de ese tipo de producciones? Tenia entendido que podian ser de la forma \( a\rightarrow{b} \) con \[ a \] y \[ b \] pertenecientes a \[ (V\cup{T}\cup{ϵ}) \] y \[ a\neq ϵ \] (donde \[ V \] variables y \[ T \] terminales)

Revisa tus apuntes. Las producciones son reglas gramaticales. En vez de escribirlas en forma de par ordenado \( (a,b) \), se escriben como \( a\to b \) y se lee "\( a \) produce \( b \)". Ello signifíca que la parte "a" puede reemplazarse por "b". Por ello, en la primera parte no puede haber terminales solas ni \( \epsilon \). Siempre al menos debe haber una variable para hacer el reemplazo.

El conjunto de producciones \( P \) es finito y \( P\subseteq(M^+\setminus T^*)\times M^* \) siendo \( M=V\cup T \). Esta definición se aplica a cualquier tipo de gramática, incluso las irrestrictas, donde no se imponen otras condiciones salvo la que acabo de escribir, para que cumpla lo mínimo requerido para formar producciones válidas.

Sobre el ejercicio que preguntabas, sugiero que esperes la respuesta de alguien más.

Saludos