Hola a todos! El ejercicio dice:
La gramática \( G=(\{A,B\},\{x,y\},A) \), donde las producciones de \( P \) están dadas por
\( \begin{array}{ccc}A&\rightarrow &x\:A/y\:B\\B&\rightarrow &x\:B/x\end{array} \)
es de tipo 3 y genera un lenguaje finito.
Cuando dice "tipo 3" se refiere a la Jerarquía de Chomsky de los tipos de gramáticas, y existen 4 tipos, donde \( G_3\subset G_2\subset G_1\subset G_0 \). Como considero que se encuentra en el tipo 3, voy a escribir la definición que tengo:
Una gramática es de Tipo 3 si toda producción \( x\to y: \)\( x \text{ es un único símbolo de los elementos no terminales;} \)
\( y \text{ es }\left\{\begin{array}{l}\text{La concatenación de 2 símbolos, siendo uno de ellos terminal,}\\\qquad\qquad\text{o}\\\text{Un único símbolo terminal,}\\\qquad\qquad\text{o}\\\text{Es la palabra nula.}\end{array}\right. \)
Con esto puedo afirmar que tanto la producción \( A\to x\: A/y\: B \) y la producción \( B\to x\: B/x \) cumplen con esos requisitos, y por tanto la gramática es de tipo 3.
Con respecto a que genera un lenguaje finito, no me puse a hacer el árbol de derivación, pero entiendo que la producción se está llamando "recursivamente"; es decir, siempre va a seguir generando palabras (pues por ejemplo \( A \) tiene dos salidas: \( x\: A \) -se genera sobre sí misma- y \( y\: B \)). Por lo tanto nunca va a generar un lenguaje finito.
¿Es correcto?
Gracias!
Saludos
Spoiler
Una pregunta media tonta: Si tenemos por ejemplo que un lenguaje generado es \( L(G)=\left\{0^{\ast} 1^{\ast}\right\} \), ¿es un lenguaje infinito?
