lenguajes y autonomas

INSTITUTO TECNOLOGICO SUPERIOR
DE
FELIPE CARRILLO PUERTO
INVESTIGACIÓN:
U1 INTRODUCCIÓN A LA TEORÍA DE LENGUAJES FORMALES.

D O C E N T E:
Ing. Marcos Gaspar Pech Cruz.

PRESENTA
Angulo Estrella Jesús Alberto
Lara Domínguez Efraín
Yama May José Luis
Tun Chulin Johnni Giovanni
Canul Chan Rolando
Estrada Canul Roger Alfredo

Aula: J2

No. De Control 111K0030
No. De Control111K0043
No. De Control 111K0056
No. De Control 111K0235
No. De Control 111K0231
No. De Control 111K0038

Grupo: B

C A R R E R A:
Ingeniería en sistemas computacionales
M A T E R I A:
Lenguajes Y Automatas

Felipe Carrillo Puerto, Quintana Roo a 28 de Enero de 2014

Introducción a la Teoría de Lenguajes Formales

Contenido
1.1 ALFABETO............................................................................................................................ 3
1.1.

CADENA ......................................................................................................................... 3

1.3 LENGUAJES .......................................................................................................................... 4
1.4 TIPOS DELENGUAJES.......................................................................................................... 4
1.5 HERRAMIENTAS COMPUTACIONALES LIGADAS CON LENGUAJES. ..................................... 6
1.6 ESTRUCTURA DE UN TRADUCTOR. ...................................................................................... 8
1.7 FASES DE UN COMPILADOR.............................................................................................. 11

ITS Carrillo Puerto

Lenguajes Y Autómatas

2
ISC-6B

Introducción a la Teoría de Lenguajes Formales

INTRODUCCIÓN TEORÍA DE LENGUAJES FORMALES.

1.1 ALFABETO
Se llama alfabeto a un conjunto finito, no vacío, cuyos elementos se denominan
“letras” o “símbolos”. Se denomina palabra a toda secuencia finita de letras
formada con los símbolos deun alfabeto. Se definen los alfabetos por la
enumeración de los símbolos que contiene.
Un "símbolo" es una entidad abstracta. Las letras y los dígitos son ejemplos
de símbolos usados con frecuencia.

Se utilizan meta–símbolos (tal como {, }, =, y la coma) para escribir sobre lo
que hablamos.
Desde el contexto siempre será claro, si se trata de un símbolo del alfabeto o si
se trata de unmeta–símbolo.
Usamos subíndices para distinguir diferentes alfabetos.
Usamos normalmente las minúsculas como alfabeto S = {a, . . . , z}, en los
ejemplos normalmente letras desde el principio del alfabeto.
Cardinalidad del alfabeto (número de elementos del alfabeto): |S| > 0, |S| < 8

1.1. CADENA
Una cadena (o palabra) es una secuencia finita de símbolos yuxtapuestos. Por
ejemplo a, b y cson 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.
Lacadena vacía, denotada por E es aquella que presenta cero apariciones
de símbolos, es una cadena que puede construirse en cualquier alfabeto.

ITS Carrillo Puerto

Lenguajes Y Autómatas

3
ISC-6B

Introducción a la Teoría de Lenguajes Formales

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, Porejemplo
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.

1.3 LENGUAJES
Un lenguaje es un conjunto de cadenas, todas ellas seleccionadas...