Cada infinita lenguaje regular no regular subconjunto?

Question

He encontrado algunos ejemplos de la infinita regular idiomas que no regulares subconjuntos. Es cierto en general?

Answer 1

Supongamos $L$ es un lenguaje regular. Desde $L$ es infinito, hay una secuencia $(w_n)$ de las palabras en $L$ tal que para todos los $n$ de la longitud de $w_{n+1}$ es mayor que el cuadrado de la longitud de $w_n$. Deje $L'=\{w_n:n\geq1\}$. La generación de la función de $L'$ es la serie $\sum_{n\geq0}t^{\operatorname{length}(w_n)}$, y esto no es una función racional. De ello se desprende que $L'$, un sublenguaje de $L$, no es normal.

La no-racionalidad de la serie se puede comprobar con la mano (los coeficientes de Taylor de la función racional satisfacer una recursividad lineal con coeficientes constantes, y la mina tiene huecos demasiado grandes para esta tarea) o el uso de algunos de los grandes como herramienta de la Ostrowski-Hadamard brecha teorema de

Answer 2

Deje $L$ ser cualquier idioma infinito. Debido a que el número de subconjuntos de a $L$ es incontable, mientras que el número de regulares de idiomas es contable, debe ser subconjuntos de a $L$ que no son regulares. El mismo razonamiento muestra que existen subconjuntos de a $L$ que no son de contexto libre, que no recursivo (decidable), y que no son recursivamente enumerable (reconocible), ya que todas estas familias de lenguas son contables.

Si un ejemplo claro es necesaria, es sencillo construir un subconjunto de a $L$ que viole el lema de bombeo para el contexto libre de idiomas, y, por tanto, que no es independiente del contexto (o regulares). Empezamos con dos vacío conjuntos, $A_{1}=B_{1}=\varnothing$. Luego repetimos los pasos siguientes para $i\in \mathbb{N}$:

1. Elija $s \in L \cap B_{i}^{c}$ que es más larga que la cadena más larga en $A_{i}$.
2. Deje $A_{i+1}=A_{i} \cup \{s \}$.
3. Deje $B_{i+1}=B_{i} \cup \{ uv^2 x y^2 z : s=uvxyz \wedge |vy|\ge 1\}$.

Debido a $L$ es infinito y $B_{i}$ es siempre finito, siempre hay una cadena disponibles para elegir en el paso 1. El conjunto $A_{\infty}=\bigcup_{i=1}^{\infty}A_{i}$ es un subconjunto de a $L$ que viole el lema de bombeo: contiene arbitrariamente largas cadenas, ninguno de los cuales puede ser de "bombeo" sin producir cadenas en el prohibido establecer $B_{\infty}=\bigcup_{i=1}^{\infty}B_{i}$, que es disjunta de a $A_{\infty}$ por la construcción. Llegamos a la conclusión de que $A_{\infty} \subseteq L$ no es independiente del contexto.

Answer 3

Sí, es cierto en general. Supongamos $L$ es un infinito de lenguaje regular. Desde $L$ es infinito, debe haber una cantidad no numerable de subconjuntos. Sin embargo, sólo hay countably muchos subconjuntos de a $L$ que son regulares idiomas. Por lo tanto, debe existir un subconjunto de a $L$ que no es un lenguaje regular.