01 Compiladores Matematicas Basicas

anterior siguiente 24/01/2011 1

Compiladores

1. Matemáticas básicas


Símbolo

Entidad abstracta que no se define formalmente como “punto” y “línea”.

Letras y dígitos

Ejemplos de símbolos: a,b,c,1,2,6.

Cadena (palabra)

Secuencia finita de símbolos yuxtapuestos: abcdba.

Longitud de una cadena ( |w| )

Es el número de símbolos que componen la cadena: abcd tiene longitud 4.

Cadena vacía ( )

Es la cadena consistente de cero símbolos.

Prefijo de una cadena

Es cualquier número de símbolos que encabezan la cadena.

Sufijo de una cadena

Es cualquier número de símbolos finales (la cola) de la cadena.

Ejemplo: abc prefijos: , a, ab, abc sufijos: , c, bc, abc

Compiladores

Conceptos preliminares sobre

Matemáticas

Cadenas, Alfabetos y Lenguajes


Un prefijo o sufijo de una cadena, diferente a la cadena misma, es llamado prefijo o

sufijo propio.

Concatenación de dos cadenas

Es la cadena formada por la primer cadena seguida de la segunda, sin espacios

intermedios. Ejemplo: dog y house concatenación doghouse.

Yuxtaposición

Es usada como el operador de concatenación. Si w y x son cadenas, wx es la

concatenación de esas cadenas.

Cadena vacía

Es la identidad para el operador de concatenación. Esto es w = w = w para cada

cadena w.

Alfabeto

Es un conjunto finito de símbolos.

Lenguaje formal

Es un conjunto de cadenas de símbolos de algún alfabeto dado.


Matemáticas

Compiladores



Conjunto vacío

El conjunto vacío ( ) y el conjunto consistente de cadenas vacías { } son lenguajes.

Nótese que son distintos; el último tiene un miembro, mientras que el primero no lo

tiene.

El conjunto de palindromes (cadenas que se leen igual hacia delante que hacia atrás)

sobre el alfabeto {0,1} es un lenguaje infinito. Algunos miembros de éste lenguaje son:

, 0, 1, 00, 11, 010 y 1101011.

Note que el conjunto de todos los palindromes sobre una colección infinita de

símbolos técnicamente no es un lenguaje porque sus cadenas no son construidas

colectivamente desde un alfabeto.

Otro lenguaje es el conjunto de todas las cadenas sobre un alfabeto fijo . Se denota

éste lenguaje por * .

Por ejemplo:

Sí = {a}, entonces * = { , a, aa, aaa, ...}

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


Matemáticas

Compiladores



Gráfica

Denotada por G=(V,E), consiste de un conjunto finito de vértices (o nodos) V y de un

conjunto de pares de vértices E llamados aristas (orillas o bordes).

Ejemplo de gráfica:

Aquí V = {1,2,3,4,5} y E = {(n,m) | n+m = 4 ó n+m = 7}.

Ruta

En una gráfica, es una secuencia de vértices v1, v2, ... vk, k 1, tal que hay una orilla

(vi, vi+1) para cada i, 1 i< k.

La longitud de la ruta es k-1. Por ejemplo: 1,3,4 es una ruta en la gráfica; sí v1 = vk la

ruta es un ciclo.


Matemáticas

Gráficas y Árboles

Compiladores

vértices

aristas


Gráfica (Grafo) Dirigida (Digraph)

Denotada por G=(V,E), consiste de un conjunto finito de vértices V y de un conjunto

de pares ordenados de vértices E llamados arcos. Se denota un arco de v a w por

v w. Por definición un grafo dirigido no acepta bucles. Un grafo que acepta bucles y

es dirigido, se llama Pseudografo dirigido.

Ejemplo de gráfica:

Gráfica dirigida ({1,2,3,4}, {i j | i < j })

Ruta en una Digraph

Es una secuencia de vértices v1, v2, ... vk, k 1, tal que vi vi+1 es un arco para cada

i, 1 i< k.. Se dice que la ruta es de v1 a vk.

Así, 1 2 3 4 es una ruta de 1 a 4 en la gráfica. Sí v w es un arco, se dice que

v es un predecesor de w, y w es un sucesor de v.


Matemáticas

Compiladores



Árboles

Un árbol (estrictamente hablando, un árbol dirigido y ordenado) es una gráfica dirigida

con las siguientes propiedades:

• Hay un vértice, llamado raíz, que no tiene predecesores y desde el cual hay

una ruta para cada vértice.

• Cada vértice diferente al raíz, tiene exactamente un predecesor.

• Los sucesores de cada vértice son ordenados “desde la izquierda”.

¿Cómo Dibujar un Árbol?

Los árboles se dibujan con la raíz en la parte superior y todos los arcos apuntando

hacia abajo. Las flechas en los arcos por lo tanto no son necesarias para indicar

direcciones y por lo tanto no se muestran.

Los sucesores de cada vértice se dibujan en orden de izquierda a derecha.

A continuación veamos la figura de un árbol y su terminología:


Matemáticas

Compiladores



Hijo

Es el sucesor de un vértice.

Padre

Es el predecesor de un vértice.

Sí hay una ruta desde el vértice v1 al vértice v2, entonces se dice que v1 es un ancestro

de v2; y v2 es un descendiente de v1. El caso v1 = v2 no es un caso excluyente;

cualquier vértice es un ancestro y descendiente de sí mismo.

Hoja

Es un vértice sin hijos, y los otros vértices son llamados vértices interiores


Matemáticas

Compiladores



A continuación veamos el ejemplo de un árbol que genera el número 123.789.


Matemáticas

Compiladores



Conjunto

Colección de objetos (miembros del conjunto) sin repetición. Los conjuntos finitos

pueden especificarse listando sus miembros entre llaves { }.

Ejemplo: {0, 1} denota el alfabeto de símbolos 0 y 1.

Especificación formal de conjuntos:

{ x | P(x) } “el conjunto de objetos x tal que P(x) es verdadero”

ó

{ x en A | P(x) } “el conjunto de x’s en el conjunto A tal que P(x) es verdadera”

y es equivalente a {x | P(x) y x está en A }.

Ejemplo: {i | i es un entero y existe un entero j tal que i = 2j }

lo cual es una forma de especificar enteros pares.


Matemáticas

Notación de Conjuntos

Compiladores


Si cada miembro de A es un miembro de B, entonces escribimos A B y se dice que

“A está contenida en B”.

A B es sinónimo de A B.

Sí A B, pero A B, esto es, cada miembro de A está en B y existe algún miembro de

B que no está en A, entonces escribimos A B (A es subconjunto propio de B).

Los conjuntos A y B son iguales si tienen los mismos miembros. Esto es, A = B, sí y

sólo sí A B y B A (entonces A es subconjunto impropio de B).

Operaciones sobre Conjuntos:

1. A B, la unión de A y B es {x | x está en A ó x está en B}

2. A B, la intersección de A y B es {x | x está en A y x está en B}

3. A – B, la diferencia de A y B es {x | x está en A y x no está en B}

4. A x B, el producto cartesiano de A y B, es el conjunto de pares ordenados (a, b)

tal que a está en A y b está en B.

5. 2A, conjunto potencia de A, es el conjunto de todos los subconjuntos de A.


Matemáticas

Compiladores



Relación

Una relación (binaria) es un conjunto de pares. El primer componente de cada par se

escoge desde un conjunto llamado Dominio, y el segundo componente de cada par se

escoge de un conjunto (posiblemente diferente) llamado Rango.

Sí el Dominio y el Rango están en el mismo conjunto S, se dice que la relación está en

S.

Si R es una relación y (a,b) es un par en R, entonces se escribirá aRb.

Propiedades de las Relaciones

Se dice que una relación R sobre el conjunto S es:

1 reflexiva, si aRa para toda a en S;

2 irreflexiva, si aRa es falsa para toda a en S;

3 transitiva, si aRb y bRc implican aRc;

4 simétrica, si aRb implica bRa;

5 asimétrica, si aRb implica que bRa es falsa.

Nótese que cualquier relación asimétrica debe ser irreflexiva.

Ejemplo: La relación < sobre el conjunto de enteros es transitiva porque a < b y b < c

implica a < c. Es asimétrica e irreflexiva porque a < b implica b < a es falso.


Matemáticas

Relaciones

Compiladores


Ejemplo: Sea A = {1, 2} y B = {2,3}, entonces

A B = {1,2,3}

A B = {2}

A – B = {1}

A x B = {(1,2), (1,3), (2,2), (2,3)}

2A = { , {1}, {2}, {1,2}}

Note que si A y B tienen n y m miembros respectivamente, entonces A x B tiene

(n x m) miembros y 2A tiene 2n miembros (2 a la n ).


Matemáticas

Compiladores



Conjuntos Infinitos

Dos conjuntos tienen la misma cardinalidad (número de miembros) si hay un mapeo

uno a uno de los elementos de S1 sobre S2.

Para conjuntos finitos, si S1 es un subconjunto propio de S2, entonces S1 y S2 tienen

diferente cardinalidad.

Sin embargo, si S1 y S2 son infinitos, la última aseveración puede ser falsa.

Ejemplo:

Sea S1 el conjunto de enteros pares y sea S2 el conjunto de todos los enteros.

Claramente S1 es un subconjunto propio de S2. Sin embargo S1 y S2 tienen la

misma cardinalidad, ya que la función definida por f(2i) = i es un mapeo uno a

uno de los enteros pares sobre los enteros.

S1 = {2 4 6 8 10 12 14 16.....} S2 = {1,2,3,4,5,6,7,8,9,10, 11,12,13,14,15,16,...}

No todos los conjuntos infinitos tienen la misma cardinalidad.


Matemáticas

Compiladores



Relaciones de Equivalencia

Una relación R que es reflexiva, simétrica y transitiva se dice que es una relación de

equivalencia.

Una propiedad importante de una relación de equivalencia R sobre un conjunto S es que

R particiones S son clases de equivalencia disjuntas y no vacías. Esto es,

S = S1 S2 ... , donde para cada i y j, con i j:

1 Si Sj = ;

2 para cada a y b en Si, aRb es verdadera;

3 para cada a en Si y b en Sj, aRb es falsa.

Las Si’s son llamadas clases de equivalencia. Nótese que el número de clases puede ser

infinito.

Una Partición o conjunto cociente de un conjunto S no vacío es la colección de los

subconjuntos o vacíos A1, A2, ... , de S tal que:

1 Ai Aj = si i j

2 Cada elemento s S pertenece a uno de los subconjuntos de Ai.


Matemáticas

Relaciones y Particiones

Compiladores


Ejemplo de una Partición:

Sea, S = {a,b,c,d,e,f,g,h}

A1 = {a,b,c,d}, A2 = {a,c,e,f,g,h}, A3 = {a,c,e,g}, A4 = {b,d}, A5 = {f,h}

{A1,A2} no es una partición ya que A1 A2

{A1,A5} no es una partición ya que e A1, y e A5

La colección {A3,A4,A5} sí es una partición de S.


Matemáticas

Particiones

Compiladores


Cerradura de Relaciones

Suponga que es un conjunto de propiedades de relaciones. La cerradura de una

relación R es la más pequeña relación R’ que incluye todos los pares de R y posee las

propiedades en .

Por ejemplo, la cerradura transitiva de R, denotada por R+, se define por:

1 Si (a,b) está en R, entonces (a,b) está en R+.

2 Si (a,b) está en R+ y (b,c) está en R, entonces (a,c) está en R+.

3 Nada está en R+ a menos que cumpla con (1) y (2).

Así, R+ incluye R, es transitiva, y contiene unos cuantos pares como cualquier relación

que incluye R y es transitiva.

La cerradura reflexiva y transitiva de R, denotada por R*, es vista como

R+ {(a,a) | a está en S}

Ejemplo: Sea R = {(1,2),(2,2),(2,3)} una relación en el conjunto {1,2,3}, entonces:

R+ = {(1,2),(2,2),(2,3),(1,3)} y R* = {(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)}


Matemáticas

Relaciones

Compiladores

Documents

01 Compiladores Matematicas Basicas