trabajos de la unidad 1
un
alfabeto
Se llama
alfabeto a un conjunto finito, no vacío, cuyos elementos se denominan “letras”
o “símbolos”. Se denomina palabra a toda secuencia finita de letras formada con
los símbolos de un alfabeto. Se definen los alfabetos por la enumeración de los
símbolos que contiene. Un "símbolo" es una entidad abstracta. Las
letras y los dígitos son ejemplos de símbolos usados con frecuencia. Se
utilizan meta–símbolos (tal como {,},
=, y la coma) para escribir sobre lo que hablamos. Desde el contexto siempre
será claro, si se trata de un símbolo del alfabeto o si se trata de un
meta–símbolo. Usamos subíndices para distinguir diferentes alfabetos. Usamos
normalmente las minúsculas como alfabeto S = {a,. . ., z}, en los ejemplos normalmente
letras desde el principio del alfabeto.
Cardinalidad del
alfabeto (número de elementos del alfabeto): |S| > 0, |S| < 8 1.1. CADENA
Una cadena (o palabra) es una secuencia finita de símbolos yuxtapuestos. Por
ejemplo a, b y c son símbolos y casa es una cadena. La longitud de una cadena w
que se denota como |w|, es el número de símbolos que componen la cadena. Por
ejemplo casa tiene una longitud 4. Habitualmente, se emplean las letras
minúsculas del principio del alfabeto (o dígitos) para designar a los símbolos
y las letras minúsculas del final del alfabeto, normalmente w, x, y y z, para
designar cadenas. La cadena vacía, denotada por E es aquella que presenta cero
apariciones de símbolos, es una cadena que puede construirse en cualquier
alfabeto.
ejemplo
Observe queΣ0 ={ ε
},independientemente de cuál sea el alfabetoΣ.Es decir, ε
es la única cadena cuya longitud
es 0. Si Σ ={0,1}, entonces Σ1 ={0,1}, Σ2 ={00,01,10,11}, Σ3 ={000,001,010,011,100,101,110,111}, etc. Observe que existe una ligera confusión entre Σ y Σ1. Lo primero es un alfabeto; sus elementos 0 y 1 son los símbolos. Lo segundo es un conjunto de cadenas; sus elementos son las cadenas 0 y 1, cuya longitud es igual a 1. No vamos a utilizar notaciones diferentes para los dos conjuntos, confiando en que el contexto deje claro si {0,1}o algún otro conjunto similar representa un alfabeto o un conjunto de cadenas.
Cadenas
Una cadena de caracteres (que también se denomina en ocasiones palabra) es una secuencia finita de símbolos seleccionados de algún alfabeto. Por ejemplo, 01101 es una cadena del alfabeto binario Σ={0,1}. La cadena 111 es otra cadena de dicho alfabeto.
Una cadena es una
secuencia finita de símbolos de un determinado alfabeto.
Eje. Tomando en
cuenta los alfabetos o vocabularios definidos anteriormente, podemos decir que:
abcb es una cadena
del alfabeto V2
a+2*b es una cadena
del alfabeto V2
000111 es una cadena
del alfabeto V3
If a>b then b=a;
es una cadena del alfabeto V4
Longitud de una cadena
Suele ser útil clasificar las cadenas por su longitud, es decir, el número de posiciones ocupadas por símbolos dentro de la cadena. Por ejemplo, 01101 tiene una longitud de 5. Es habitual decir que la longitud de una cadena es igual al “número de símbolos” que contiene; esta proposición está aceptada coloquial mente, sin embargo, no es estrictamente correcta. Así, en la cadena 01101 sólo hay dos símbolos, 0 y 1, aunque tiene cinco posiciones para los mismos y su longitud es igual a 5. Sin embargo, generalmente podremos utilizar la expresión “número de símbolos” cuando realmente a lo que se está haciendo referencia es al “número de posiciones”.
Lenguajes
Un conjunto de cadenas, todas ellas seleccionadas de un Σ∗, donde Σ es un determinado alfabeto se denomina lenguaje.SiΣes un alfabeto y L⊆Σ∗, entonces Les un lenguaje de Σ. Observe que un lenguaje deΣno necesita 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 superiormente de Σ. La elección del término “lenguaje” puede parecer extraña. Sin embargo, los lenguajes habituales pueden interpretarse como conjuntos de cadenas.Un ejemplo sería el inglés,donde la colección de las palabras correctas 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 cadenas que pueden formarse a partir del alfabeto del lenguaje. Este alfabeto es un subconjunto de los caracteres ASCII. El alfabeto en concreto puede diferir ligeramente entre diferentes lenguajes de programación, aunque generalmente incluye las letras mayúsculas y minúsculas,los dígitos,los caracteres de puntuación y los símbolos matemáticos.
Conjunto de sonidos articulados con que el hombre manifiesta lo que piensa o siente. Sistema de comunicación verbal. Manera de expresarse. Conjunto de señales que dan a entender algo. El lenguaje de los ojos, el de las flores. En Informática Conjunto de signos y reglas que permite la comunicación con un ordenador. Microsoft Encarta 2007. 1993-2006 Microsoft Corporation. Reservados todos los derechos.
Podemos expresarlo de manera más sencilla como un conjunto de palabras ó cadenas de símbolos (palabras, oraciones, textos o frases) de un determinado alfabeto.
LENGUAJE VACÍO
Existe un lenguaje denominado lenguaje vacío, que es un conjunto vacío y que se denota por {Ø}. El lenguaje vacío no debe confundirse con un lenguaje que contenga una sola cadena, y que ésta sea la cadena vacía, es decir {l}, ya que el número de elementos (cardinalidad) de estos dos conjuntos es diferente.
Cardinal ({ Ø }) = 0
Cardinal ({ l }) = 1
Comentarios
Publicar un comentario