lenguaje libre de contexto probar o refutar

Question

Tengo que probar o refutar que para cada idioma $L$ que tiene las propiedades:

1. para cada longitud no-prima hay al menos una palabra en L.

2. para cada longitud prima ninguna de las palabras está en L.

no es un lenguaje libre de contexto.

Creo que es cierto y que no hay ningún lenguaje libre de contexto que tenga las dos propiedades anteriores pero estoy atascado.

Answer 1

Pista: Pruebe a utilizar el lema de bombeo para lenguajes libres de contexto, y Teorema de Dirichlet sobre la infinidad de primos en ciertas progresiones aritméticas para demostrar que las dos condiciones son inconsistentes con $\ L$ al estar libre de contexto.

Deberías ser capaz de demostrar que bajo la primera condición dada, si $\ L\ $ fueran libres de contexto, tendría que existir una palabra $\ uvwxy \ $ , bombeable a $\ uv^nwx^ny\ $ para cualquier número entero positivo $\ n\ $ en el que $\ \vert uvwxy\,\vert\ $ (y por lo tanto también $\ \vert uwy\,\vert\ $ ) es relativamente primo de $\ \vert vx\,\vert\ $ . Del teorema de Dirichlet se deduce que $\ L\ $ debe contener una palabra de longitud prima.

Answer 2

Ambas afirmaciones son erróneas. Sea $A$ sea un alfabeto no vacío.

Toma $L = A^*$ que, por supuesto, es libre de contexto. Para cada longitud $n$ (no primo o no), hay una palabra de longitud $n$ en $L$ . Por tanto, se cumple (1).

Ahora toma $L = \emptyset$ que también es libre de contexto. Entonces, para cada longitud $n$ (primo o no), no hay ninguna palabra de longitud $n$ en $L$ . Por tanto, (2) se cumple.

EDITAR . Un lenguaje que satisfaga simultáneamente (1) y (2) no puede ser libre de contexto. En efecto, sea $f: A^* \to a^*$ sea el homomorfismo monoide definido por $f(u) = a^{|u|}$ y que $K = f(L)$ . Por las condiciones (1) y (2), se obtiene $$K = \{a^p \mid \text{$ p $ is not prime} \}$$

Si $L$ era libre de contexto, entonces $K$ sería libre de contexto, ya que los lenguajes libres de contexto son cerrados bajo homomorfismos. Además, un lenguaje libre de contexto en un alfabeto de una letra es regular (es un caso especial de Teorema de Parikh ). Ahora se puede concluir utilizando el lema de bombeo (véase esta respuesta para más detalles).