Lenguajes y Autómatas II

21/02/2013

LENGUAJES Y AUTOMATAS
UNIDAD I:
INTRODUCCION A LA TEORÍA DE
LENGUAJES FORMALES

INDICE
•
•
•
•
•
•
•
•

1.1 Alfabeto.
1.2 Cadenas.
1.3 Lenguajes
1.4 Tipos de lenguajes
1.5 Herramientas computacionales ligadas
con lenguajes
1.6 Estructura de un traductor
1.7 Fases de un compilador

1

21/02/2013

3

INTRODUCCION A LA TEORÍA DE
LENGUAJES FORMALES
Losconjuntos
X={1,2,3}
Y={a,b,c,d}
Se definen de una manera explícita.
Los conjuntos que contienen un número finíto muy
largo de miembros o un número infiníto
miembros se definen de manera implícita.
Ejemplo: El conjunto de todos los cuadrados
perfectos es definido como:
{n | n=m2 para algún número natural m}
El conjunto vacío se representa por 0, y es el
conjunto que no tiene miembros, osea que
={}

0

1.1 Alfabeto.

2

21/02/2013

1.1 ALFABETO
Un alfabeto consiste de un conjunto finito de objetos no
divisibles. El alfabeto de un lenguaje se represent por S.
El alfabeto de un lenguaje natural como el español consiste
de las palabras de el lenguaje.
1.1 Alfabeto.

Comúnmente los elementos de un alfabeto se
representan por caracteres únicos como letras (a,b,c) odígitos (1,2,3).
Ejemplo: Sea ={a,b,c}. Las siguientes son cadenas de ese
alfabeto: abc, ccb, cab,aaaabbbccc
5

1.2 Cadena.

3

21/02/2013

7

1.2. CADENA
Una cadena de un conjunto X es una secuencia
finíta de elementos de X.
Las cadenas son objetos fundamentales usados en
la definición de lenguajes.
El conjunto de elementos de donde las cadenas son
producidas son llamadosalfabetos de el lenguaje.

8

La cadena que contiene cero elementos es llamada cadena
nula o vacía y se representa por l.
La concatenación de dos cadenas u y v, escrita uv, es “pegar”
las dos cadenas para formar una nueva.
Ejemplo:
Sea u=ab , v=ca y w=bb.
Entonces
uv=abca
(uv)w=abcabb

vw=cabb
u(vw)=abcabb

El resultado de la concatenación de u,v y w es independiente
de el orden enque las operaciones son ejecutadas.
Matematicamente esta propiedad es conocida como asociatividad.

4

21/02/2013

1.3 Lenguaje.

10

La longitud o tamaño de una cadena w es el número de
elementos que contiene la cadena.
Ejemplo: La cadena abcdef tiene una longitud de 6.
Una subcadena u de la cadena v existe si existen las
cadenas x y y de tal forma que v = xuy.
Esto quiere decirQue u “ocurre dentro de” v.
Un prefijo de v es una subcadena u en donde x es la
cadena vacía en la descomposición de v.
Eso quiere decir que v=uy.
Similarmente, u es un sufijo de v si v=xu.
Ejemplo: ab es un prefijo de la cadena abcdef y ef es un
sufijo de la misma cadena.

5

21/02/2013

11

1.3. LENGUAJE
Un lenguaje consiste de un grupo de cadenas de un alfabeto.
Usualmenteciertas restricciones se aplican a las cadenas del lenguaje.
Por ejemplo el lenguaje Español consiste de todas las cadenas de palabras que
nosotros llamamos oraciones.
No todas las combinaciones de palabras forman oraciones. De alli que un
lenguaje consiste de un subconjunto de el conjunto de todas las posibles cadenas
que se pueden formar de el alfabeto.
Ejemplo: El lenguaje L de cadenas de elalfabeto {a,b} en donde cada cadena
comienza con una a y tiene longitud par. Las cadenas
aa, ab, aaaa, abbb, abab, abbbaaba
forman parte de ese lenguaje.

12

El lenguaje anterior se puede definir recursivamente
como:
i) Base: aa, ab son miembros de L.
ii) Paso recursivo: Si u es miembro de L, Entonces
uaa, uab, uba, ubb son miembros de
L.
iii) Cierre (Closure): Una cadena u esmiembro de L
solo si puede
ser obtenida de los elementos base por un
número finíto
de aplicaciones del paso recursivo.

6

21/02/2013

13

Ejemplo: El lenguaje L consiste de cadenas del alfabeto {a,b}
en donde cada ocurrencia de b es inmediatamente precedida
por una a. Por ejemplo, l, a, abaab estan en L y bb, bab, abb
no estan en L.
i) Base: l es miembro de L.
ii) Paso recursivo:...