Si un alfabeto $= \{a, b\}$
Creo que un ejemplo de lenguaje finito sobre ese alfabeto con cardinalidad positiva sería el conjunto igual a $(a+b)^4$
Un ejemplo de lenguaje contablemente infinito sobre el alfabeto sería ${a}^*$
Pero, ¿existen los lenguajes incontablemente infinitos? Cada elemento (cadena) del lenguaje es finito, por lo que creo que se podría establecer una relación de uno a uno con el conjunto de los números enteros.
En la teoría elemental de la computabilidad, solemos trabajar con lenguajes que son subconjuntos de $\mathbb{N}$ o que están en biyección con subconjuntos de $\mathbb{N}$ como los lenguajes formados por palabras finitas sobre un alfabeto finito.
En niveles más avanzados de la teoría de la computabilidad, también nos ocupamos de colecciones más generales, como las colecciones cuyos elementos son secuencias infinitas de un alfabeto finito o contable. Al igual que los lenguajes contables, podemos utilizar las máquinas de Turing para definir qué significa que uno de estos "lenguajes" incontables sea decidible, semidecidible, etc. La analogía más general es a través de la jerarquía aritmética . Esto nos permite hacer definiciones similares para subconjuntos de $\mathbb{N}$ subconjuntos de $\mathbb{2}^\mathbb{N}$ y subconjuntos de $\mathbb{N}^\mathbb{N}$ .
Sin embargo, puede que no sea muy habitual llamar "lenguas" a estas colecciones incontables. Por ejemplo, a menudo estamos interesados en un "lenguaje" que consiste en todos los caminos infinitos a través de algún subárbol computable del árbol binario completo. En lugar de llamar a estos "lenguajes", solemos denominarlos " $\Pi^0_1$ clases ".
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
