Lenguajes

1. INTRODUCCIÓN A LA TEORÍA DE LENGUAJES

FORMALES.

 Alfabeto:

El término alfabeto procede del griego ἀλφάβετον (alfábeton), derivado de las dos primeras letras griegas ἄλφα (alfa, α) y βῆτα (beta, β), derivadas a su vez de las letrasfenicias ʾalp y bēt, que significaban ‘buey’ y ‘casa’ respectivamente.

En otros ámbitos (matemáticas, y otros sistemas formales, por ejemplo), un alfabeto es un conjunto finito y ordenado de símbolos a partir del cual se construyen palabras y fórmulas bien formadas.

Conjunto finito de símbolos. Un alfabeto se indica normalmente con ∑ o , que es el conjunto de letras en un alfabeto.

Ejemplos:

{0,1}

{a, b, c, …, x, y, z}

{0,1, 2, 3, 4, 5, 6, 7, 8, 9,}

{a, b}

 Cadena:

Un "símbolo" es una entidad abstracta. Las letras y los dígitos son ejemplos de símbolos usados con frecuencia. 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.

La concatenación de dos cadenas es la cadena que se forma al escribir la primera seguida de la segunda, sin que haya espacio entre ellas, Por ejemplo la concatenación de padre y madre es padremadre. La yuxtaposición se utiliza como el operador de concatenación. Esto es si w y x son cadenas, entonces wx es la concatenación de estas dos cadenas. La cadena vacía es la identidad para el operador de concatenación, es decir Ew=wE para cada cadena de w.

 Lenguajes:

Un lenguaje es un conjunto de cadenas, todas ellas seleccionadas de un S* donde S es un determinado alfabeto

El conjunto vacío Ø y el conjunto formado por la cadena vacía { E } son lenguajes.

El conjunto de palíndromos (cadenas que se leen igual de izquierda a derecha y viceversa) sobre el alfabeto {0,1} es un lenguaje infinito.

Algunos elementos de este lenguaje son E,0,1, 00, 01,010, y 1101011.

Por consiguiente vemos que el conjunto de todos los palíndromos sobre una colección finita de símbolos no es, técnicamente hablando, un lenguaje, porque sus cadenas no se construyen colectivamente a partir de un alfabeto.

Otro lenguaje es el conjunto de cadenas sobre un alfabeto fijo S Denotamos a este lenguaje como S* Por ejemplo:

Si S = {a}, entonces S* = {E, a, aa, aaa,...}.

Si S = {0,1}, entonces S* = {E,0,1,00,01,10,11,000,...}

Como comentamos anteriormente el asterisco (*) representa cualquier número de apariciones de la expresión anterior.

 Tipos de lenguajes:

EJEMPLO CON UN LENGUAJE NATURAL (CASTELLANO)

Estamos familiarizados con el concepto tradicional de gramática que, de forma intuitiva, podríamos considerar como un conjunto de reglas que nos indican que es

Correcto y que no lo es en un lenguaje natural. Con el fin de acercarnos a una definición más formal comenzaremos con un ejemplo en lengua castellana.

La gramática debe describir la estructura de las frases y de las palabras de un lenguaje. Veamos una serie de reglas muy sencillas que nos permitirían comprobar que la frase “el perro corre deprisa” es correcta.

Reglas gramaticales:

...