1.3 Lenguajes, tipos y herramientas

 1.5.3. Lenguajes

Un conjunto de cadenas, todas ellas seleccionadas de un Σ* es un determinado alfabeto se lenguaje.

 Si Σ es unalfabetoyL ⊆Σ∗,entonces L esunlenguajede Σ.ObservequeunlenguajedeΣnonecesita incluir cadenas con todos los símbolos de Σ, ya que una vez que hemos establecido que L es un lenguaje de Σ, también sabemos que es un lenguaje de cualquier alfabeto que sea un superconjunto de Σ.

La elección del término “lenguaje” puede parecer extraña. Sin embargo, los lenguajes habituales pueden interpretarse comoconjuntosdecadenas.Unejemploseríael inglés,dondelacoleccióndelas palabrascorrectas inglesas es un conjunto de cadenas del alfabeto que consta de todas las letras. Otro ejemplo es el lenguaje C, o cualquier otro lenguaje de programación, donde los programas correctos son un subconjunto de las posibles cadenasquepuedenformarseapartirdelalfabetodel lenguaje.Este alfabeto es un subconjuntode los caracteres ASCII. El alfabeto en concreto puede diferir ligeramente entre diferentes lenguajes de programación, aunque generalmenteincluyelasletrasmayúsculasyminúsculas,losdígitos,loscaracteresdepuntuaciónylossímbolos matemáticos.

1. El lenguaje de todas las cadenas que constan de n ceros seguidos de n unos para cualquier n ≥ 0: {ε,01,0011,000111,...}. 2. El conjunto de cadenas formadas por el mismo número de ceros que de unos: {ε,01,10,0011,0101,1001,...} 3. El conjunto de números binarios cuyo valor es un número primo: {10,11,101,111,1011,...} 4. Σ∗ es un lenguaje para cualquier alfabeto Σ. 5. /0, el lenguaje vacío, es un lenguaje de cualquier alfabeto. 6. {ε},el lenguajequeconstasólo delacadenavacía, tambiénesun lenguajedecualquieralfabeto.Observe que /0= {ε}; el primero no contiene ninguna cadena y el segundo sólo tiene una cadena.

La unica restriccion importante sobre lo que puede ser un lenguaje es que todos los alfabetos son finitos