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

...