Escuela de Ingeniería de Sistemas

Curso: Teoría de Lenguajes y Compiladores

Sesión 1:
Introducción a la Teoría de Lenguajes Formales

Mg. Julissa Reyna González

Email: jreyna@[Link]
Conceptos sin intuiciones son vacíos,
intuiciones sin conceptos son ciegas.
Inmanuel Kant
 Respondemos
Go to [Link] and use the code 4321 9317
 Principios
• Euclides
• Babilonios
• Diseño de Algoritmos
• Complejidad asintótica y reducibilidad.
La ciencia de la computación es el cuerpo sistematizado del
conocimiento acerca del cálculo.
 La Teoría de la Computación tiene sus inicios en
varios campos distintos.

• Biología: Modelos de redes Neuronales.

• Ing. Eléctrica: Teoría de la interrupción para diseño de Hw.

• Matemáticas: Fundamentos de la lógica.

• Lingüística: Gramáticas de los lenguajes naturales.

 PRELIMINARES MATEMÁTICOS
Teoría de conjuntos
Un conjunto es una colección de elementos
donde: L= {a, b, c, d} elementos del alfabeto
b Є L especifica que b es un elemento del conjunto L
r ∉ L especifica que r no es un elemento del conjunto L
En un conjunto no se distinguen repeticiones de los elementos
{a, b, c, d}={a, b, c, b, a, c, d}
El orden no tiene ningún significado
{a, b, c, d}={b, a, d, c}
Dos conjunto son iguales si y solo si tienen los mismos elementos
 PRELIMINARES MATEMÁTICOS
Teoría de conjuntos
Un conjunto puede tener un solo elemento y se llama simple.
{1} tiene un solo elemento {1} y 1 son distintos
El conjunto que no tiene elementos se denomina conjunto vacío y se denota
con Ø, {}
Se pueden especificar conjuntos listando sus elementos separados por
comas y entre llaves.
Donde: {a, b, c, d, e, f, g, h, i, j}
Algunos no pueden ser descritos de esta forma por que son infinitos.
|N = {0,1,2,3,4,5,... }
Un conjunto que no es infinito se denomina finito.
 PRELIMINARES MATEMÁTICOS
Teoría de conjuntos
Otra manera de especificar un conjunto es por referencia a otros
conjuntos y a propiedades que pueda o no tener.
G={x | x Є A “and” x > 32 }
en general se especifica:
B= {x | x Є A and x tiene la propiedad P}
• Un conjunto es subconjunto de otro sí cada elemento de A es
también elemento de B; se especifica A ⊆ B
• Un conjunto es subconjunto de sí mismo. Si A ⊆ B pero A no es el
mismo B, A es subconjunto propio de B. El conjunto vacío es
subconjunto de todo conjunto.
 PRELIMINARES MATEMÁTICOS
Teoría de conjuntos
Los conjuntos pueden combinarse para formar un tercero por varias operaciones
de conjuntos.
La unión de dos conjuntos es el conjunto que tiene como elementos aquellos que
son elementos de al menos uno de los conjuntos y tal vez de ambos.
A U B = {x | x Є A or x Є B}
La intersección de dos conjuntos es la colección de elementos que los dos
conjuntos tienen en común
A ∩ B = {x | x Є A and x Є B}

La diferencia de dos conjuntos A y B, denotada A - B es el conjunto de elementos

de A que no son elementos de B.
A - B = {x | x Є A and x ∉ B}Dos conjuntos son disjuntos si no tienen elementos en
común, es decir si su intersección es el conjunto vacío.
 PRELIMINARES MATEMÁTICOS
Teoría de conjuntos
El conjunto potencia de un conjunto A es el conjunto de todos sus
subconjuntos y se denota por 2A.
Una partición de un conjunto no vacío A es un subconjunto ∏ de 2A tal
que f no es elemento de ∏ y cada elemento de A esta en uno y solo un
conjunto de ∏
∏ es una partición de A si ∏ es un conjunto de subconjuntos de A tales
que:
1. Cada elemento de ∏ es no vacío
2. Distintos miembros de ∏ son disjuntos
3. U∏ = A
 PRELIMINARES MATEMÁTICOS
Relaciones y Funciones
• Producto cartesiano
Operación de conjuntos que construye un conjunto que consiste de
pares ordenados de elementos a partir de dos conjuntos existentes
Se define como:
X x Y = {(x, y) | x Є X and y Є Y}
Una relación binaria entre dos conjuntos X y Y es un subconjunto del
producto cartesiano.
El producto se puede generalizar a varios conjuntos X1,X2,X3,...,Xn.
 PRELIMINARES MATEMÁTICOS
Funciones
En forma intuitiva, una función es un mapeo o asociación de elementos de un
conjunto con elementos de otro conjunto; se denota:
f : x -> y.
De manera formal una función de un conjunto X a un conjunto y es una relación
binaria R sobre X y Y con la siguiente propiedad: para cada elemento a Є X, hay
exactamente un par ordenado en R con a como primer elemento.
f(x) denota el elemento de y asignado a un elemento x Є X.
X es el dominio, el rango de f es el subconjunto de Y consistente de los miembros
de Y que son asignados a elementos de X
Rango = {y Є Y | y = f(x) para alguna x Є X}
 Teoría de Lenguaje Formal

Un lenguaje formal es un conjunto (finito o infinito) de cadenas finitas de

símbolos primitivos Ej: El lenguaje “Número” es simplemente el conjunto
infinito de cadenas finitas formadas con los dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9.
Dichas cadenas están formadas gracias a un alfabeto y a una gramática que
están formalmente especificados.
 El alfabeto es un conjunto finito no vacío de símbolos.
La gramática es un conjunto finito de reglas para formar cadenas finitas
juntando símbolos del alfabeto.
A cada cadena de símbolos de un lenguaje formal se le llama fórmula bien
formada (o palabra) del lenguaje.
 Tipos de Lenguajes Formales
LENGUAJE NATURAL (CASTELLANO):

Nosotros estamos relacionados con el concepto tradicional de gramática que, de

esta forma intuitiva, podemos considerar un conjunto de reglas el cual nos
indican que es correcto y que no lo es del, lenguaje natural.

LENGUAJE ARTIFICIAL:
En este lenguaje aplicamos el mismo método en el cual definimos un fragmento
del lenguaje de programación. Donde pretendemos describir las instrucciones el
cual nos permite asignar un valor a una expresión ó a una variable en un
lenguaje C.
 Tipos de Lenguajes Formales

LENGUAJE REGULAR:

Llamamos así a los lenguajes porque sus palabras contienen

"regularidades" o repeticiones de los mismos componentes, por ejemplo
en este lenguaje L1 = { ab, abab, ababab, abababab,...} Este ejemplo
podemos apreciar las palabras de L1 son solo repeticiones de "ab" donde
se repiten varias veces. Su regularidad consiste en las palabras que
contienen "ab" varias veces.
 Alfabetos, cadenas y lenguajes
Symbols : elements indivisibles
a 1 perro

algo nada

entren para for

Un alfabeto es un conjunto de símbolos (Formalmente, un conjunto no vacío y finito de símbolos).

Se denota con Σ.
• letras = {a, b, c, d, e, f, g, .... , z}
• dígitos = {0,1,2,3,4,5,6,7,8,9}
• palabras = {a, en, nada, león, Pedro, si, entrada}
• keywords = {main, void, do, while, if, for, .... }
 Alfabetos, cadenas y lenguajes

Observamos el video:

[Link]
 Alfabeto (Σ)

Definición: Un alfabeto Σ es un conjunto finito de símbolos.

Σ = 0 El alfabeto es no vacio.
| Σ | > 0 La cardinalidad del conjunto es mayor a cero.
Ejemplo:
Σ = { a,b,c,d,e…z} Alfabeto del Lenguaje español.
Σ = { 0,1,2,3,…9} Alfabeto numerico.
Σ = { 0,1} Alfabeto binario.
Σ = { 0,1,…9, A,B,C,…F} Alfabeto Hexadecimal.
 Alfabeto (Σ)
Actividad:
Σ = { a,b,c,d,e…z} Alfabeto del Lenguaje español.
Σ = { 0,1,2,3,…9} Alfabeto numerico.
Σ = { 0,1} Alfabeto binario.
Σ = { 0,1,…9, A,B,C,…F} Alfabeto Hexadecimal
Escribe  y  según corresponda el symbol o character de los
alfabetos dados:
a) B ___ Σ e) e ___ Σ
b) 0 ___ Σ f) F ___ Σ
c) 9 ___ Σ g) 10 ___ Σ
d) x ___ Σ h) A3 ___ Σ
 Palabra o Cadena (w)

Una cadena o palabra es la sucesión de simbolos de un

determinado alfabeto.
Ejemplo:
Sea Σ = { 0,1}
w1 =01101 LONGITUD DE UNA PALABRA O CADENA
| w1 | = 5
w2 =0 | w2 | = 1
| w3 | = 0
w3 = 
Cadena vacía
 SUPERINDICES

Ejemplo:
Sea Σ = { 0,1}
Σ = {} entonces es la única palabra de tamaño 0.
Σ ¹= {0,1} entonces es = ? Σ
Σ ²= {00,01,10,11} entonces son todas las palabras de tamaño 2.
Σ ³= {000,010,001,100,101,110,111} entonces son todas las
palabras de tamaño 3.
 CLAUSURA DE KLEENE

Σ* = Σ U Σ¹ U Σ² U Σ³ U…
Σ† = Σ* - {}
ĸ ĸ-1
Σ =ΣxΣ
Combinación
de palabras
 Longitud de una cadena

Definición: La longitud de la cadena xy

Se denota |xy| es = |x| + |y| = n+m. Si n + m = 0, el largo es ε,
o la hilera vacía.

Definición: Tenemos 2 cadenas:

s = s1s2…sn
t = t1t2…tm,
la concatenación de s y t se denota st, y al concatenar
obtenemos la hilera s1s2…snt1t2…tm.
st= s1s2…snt1t2…tm.
 Prefijo, sufijo y substring

Definición: Tenemos 2 cadenas:

s = s1s2…sn
t = t1t2…tm,
Se pide obtener st= s1s2…snt1t2…tm.

prefijo
st sxt

sufijo Subcadena
o sub string
 Prefijo, sufijo y substring

Ejemplo: Tenemos la cadena: x= 0110

Se pide obtener.

prefijo Subcadena sufijo

o sub string

0,01,011 0,10,110
1,11
 Prefijo, sufijo y substring

Ejemplo: Tenemos la cadena: y= 10011

Se pide obtener.

prefijo Subcadena sufijo

o sub string
 Lenguaje (L) sobre un alfabeto (Σ)

Definición: Un lenguaje L sobre un alfabeto Σ es un subconjunto de

Σ*.
Se representa: L  Σ*
 Lenguaje (L) sobre un alfabeto (Σ)

Ejemplo: Σ = {a, b}.

L1 = ø es un lenguaje
L2 = {ε} es un lenguaje
L3 = {a} es un lenguaje
L4 = {a, ba, bbab} es un lenguaje
L5 = {anbn / n >= 0} es un lenguaje
donde an = aa…a, n veces
L6 = {a, aa, aaa, …} es un lenguaje
• Nota: L5 es un lenguaje infinito, pero descrito finitamente.
 Lenguaje (L) sobre un alfabeto (Σ)

Ejemplo: Σ = {a, b}.

(Σ*, ·) a
aa
a aba
a b
a ab b
abb
ε
b
a ba
b b
bb

Σ* es contablemente infinito: no se puede calcular todo Σ*. Solo se

pueden calcular subconjuntos finitos de Σ*. Pero SÍ se puede
calcular si una hilera dada pertenece a Σ*.
 Concatenación (.)

Definición: La concatenación (o producto) de dos lenguajes L1 y L2,

se denota L1.L2, = L1L2 y es el conjunto {xy | xL1 ^ yL2}.

Ejemplo: L1 = {ε, a, bb}, L2 = {ac, c}

L1L2 = {ac, c, aac, ac, bbac, bbc}
L1L2 = {ac, c, aac, bbac, bbc}
 Concatenación (.)

Ejemplo: L1 = {ab, b}, L2 = {ac, c}

L1 L2 = { }
L1L2 = { }
 Disjunción (/)

Definición: La disjunción de dos lenguajes L1 y L2, se denota L1/L2,

es el conjunto {x/x L1 v x L2}.

Ejemplo: L1 = {ε, a, bb}, L2 = {ac, c}

L1/L2 = {ac, c, aac, ac, bbac, bbc}
 Potencia

Definición: Ln = LL…L (n veces),

y L0 = {ε}.

Ejemplo: L = {a, bb}

L3 = {aaa, aabb, abba, abbbb, bbaa, bbabb, bbbba, bbbbbb}

 Otros constructores de Lenguajes
Definición: La unión de dos lenguajes L1 y L2 es el conjunto L1 L2
= {u | uL1} { v | vL2}

Definición: La clausura de Kleene (L*) de un lenguaje es el

conjunto L* = U Ln, n >0.

Ejemplo: L = {a, bb}

L* = {cualquier hilera compuesta de a’s y bb’s}

Definición: La clausura transitiva(L+) de un lenguaje L es el

conjunto L+ = U Ln, n > 1.
 Otros constructores de Lenguajes
Nota:
En general, L* = L+ U {ε}, pero L+ ≠ L* - {ε}.

Por ejemplo, considerar L = {ε}. Entonces

{ε} = L+ ≠ L* – {ε} = {ε} – {ε} = ø.
 Ejercicio:

Sea el Σ = {a,b}
L = {aba,bab,a,b,abbb}.
Halle las cadenas de L y la longitud de cada cadena:

w1 = | w1 | =
w2 = | w2| =
w3 =
w4 =
w5 =
Alfabetos, cadenas y lenguajes
Alfabetos, cadenas y lenguajes
Alfabetos, cadenas y lenguajes
 Referencias

• Aho, Lam, Sethy, Ullman (2008). Compiladores principios, técnicas y

herramientas.
• Kenneth C. Louden (2004). Construcción de compiladores. Alfonseca.
• Ortega, Pulido (2006). Compiladores e intérpretes.
• Brookshear J.(1989). Teoría de la computación, lenguajes formales,
autómatas y complejidad.
• Adisson-Wesley. (1989). Wilmington Delaware EUA
• Augusto Cortez Vásquez.(2005). Lenguajes y traductores.
 Actividad Asincronica
• Responder formulario (Google form).
• Elabora un mapa mental de la Teoría de Lenguajes haciendo uso de la
herramienta [Link] (Trabajo grupal)