Dada la lengua $$L = \{ a^p \mid p\, \text{IS NOT prime} \}$$ is $L$ Contexto libre? Si no, probar que no lo es.
Tengo algunas sugerencias sobre cómo utilizar el lema de bombeo para probar esto, por favor?
Gracias.
Respuesta
¿Demasiados anuncios?
frabala
Puntos
1709
No sé si se te pide que utilizar necesariamente el lema de bombeo con el fin de resolver el problema, pero en este caso de la lengua, es mucho más fácil de usar Parikh del teorema.
El alfabeto de la lengua es $\Sigma=\{a\}$. Así, por cada palabra $w$, Parikh del vector es $P(w)=|w|_{a}$ (que es el número de ocurrencias de $a$$w$). Entonces, el conjunto de Parikh de los vectores de lenguaje $L$ del ejercicio es el conjunto de números divisibles. $$S=\{P(w):w\in L\}=\{|a^p|: p~\text{not prime}\}=\{p:p~\text{not prime}\}$$
Es fácil demostrar que este juego no es semi-lineal, ya que no finita de la unión de los conjuntos puede resultar a $S$. Si hay una unión, un número divisible falta, que conduce a la contradicción.
