compiladores

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Educación Superior
Universidad Valle del Momboy
UVM-Estovacuy









ALFABETO, PALABRAS Y LENGUAJES

Lenguajes formales




Integrantes:
Pacheco Rosa
Méndez Víctor
Valero Renzo
Profesora: Hellys Mendoza

Carvajal, 18 de Septiembre de 2013
Introducción

Los compiladores tienen lahabilidad de traducción de lenguajes que casi siempre consisten en elementos sintácticos que pueden ser descritos de manera más formal.
Los lenguajes pueden ser extensos con muchas y variadas combinaciones, para entender un poco más este tema debe saberse aspectos teóricos del mismo:
Por ejemplo:
Una secuencia de símbolos de cualquier alfabeto es conocido como una palabra.
Una cadena es unasecuencia de palabras unidas entre sí.
Un símbolo es denominado como un elemento de un vocabulario.
Estos aspectos son comunes en nuestra vida diaria, al igual un compilador necesita estas definiciones para realizar su trabajo.







Alfabetos, palabras y lenguajes

Un símbolo es un signo, digito, letra o incluso un grupo de letras que se utiliza en algún lenguaje y que tiene algúnsignificado por sí mismo. De forma similar, la representación de enteros son secuencias de caracteres del conjunto de los dígitos {0,1,2,3,4,5,6,7,8,9}

EJEMPLOS DE SIMBOLOS: 0, 1, W, Ok, b, Ω, ∑, etc.

Un alfabeto es un conjunto finito no vacio de símbolos y se denota por ∑.

EJEMPLO 1
∑= {0,1} es un alfabeto

EJEMPLO 2
El alfabeto griego es ∑= {ε, θ, λ,….., μ, β, δ, ε, ω}

EJEMPLO3
Otro alfabeto puede ser: ∑= {READ, INPUT, GET, FOR, ….IF}



Propiedades de los alfabetos

Los alfabetos comparten las propiedades que son comunes a cualquier otra clase de conjuntos, es decir, sean ∑1 y∑2 son dos alfabetos, entonces si el resultado de las siguientes operaciones:
, , ,  Son conjuntos no vacios, son alfabetos.

EJEMPLO 1
Sean los alfabetos  y,entonces tenemos que también son alfabetos los siguientes:







Palabras o Cadenas
Una cadena o palabra es una secuencia finita de simbolos yuxtapuestos de un alfabeto dado.

EJEMPLO 1
Sea , entonces w1=10, w2=10011 y w3=100100101 son cadenas o palabras formadas a partir del alfabeto.

EJEMPLO 2
Sea , x1=adce, x2=aaaaa, x3=cabe, x4=decada y x5=c son cadenas o palabras formadas apartir de ese alfabeto.
Cadena Vacía
La cadena vacía se denota por ε y es la cadena que está formada por una secuencia vacía de simbolos bajo cualquier alfabeto.

Operaciones con cadenas o palabras
Longitud de una cadena
Si w es una cadena, decimos que la longitud de la misma es el numero de simbolos que la forman y se denota por |w|.

EJEMPLO 1

Sea w1=101011, entonces |w1|=6 y seaw2=10110100101, entonces |w2|=11.
La longitud de la cadena vacía es cero: | ε |=0


Concatenación
Concatenación es yuxtaposición de dos cadenas, una a continuación de la otra, de tal forma que si w y x son dos cadenas, la concatenación de w con x es la cadena que se obtiene de añadir x a la cadena w. La concatenación se denota con el operador de yuxtaposición: , pero usualmente se omiteel punto, quedando wx.

EJEMPLO 1
Sea w= sofá y x=cama entonces =sofacama, mientras que =camasofa.

La longitud de la concatenación es igual a la suma de las longitudes de las cadenas individuales: |wx|=|w|+|x|.

En el ejemplo anterior w y x son dos cadenas de longitud 4 y  es de longitud 8.

EJEMPLO 2:
Sean w=so y x=pa, entonces xw=paso y wx=sopa.

La concatenación de ε concualquier cadena w no modifica a w. Es decir, la cadena vacía es el idéntico respecto a la concatenación, ya que: εw=wε=w.


Ejemplo 3 
Si Σ = {a, b, c}, A = {a, ab, ac}, B = {b, b2}
AB = {ab, ab2, ab2, ab3, acb, acb2}
BA = {ba, bab, bac, b2a, b2ab, b2ac}

Propiedades de la Concatenacion

1. AB = BA
2. A.∅ = ∅.A = ∅
3. A.{ε} = {ε}.A = A
4. A.(B.C ) = (A.B).C (ley asociativa)...