ndice

Introduccin ................................................................................................................................. 1
1.1 Alfabeto ............................................................................................................................. 2
1.2 Cadenas ............................................................................................................................. 3
1.3 Lenguajes ........................................................................................................................... 4
1.4 Tipos de lenguajes ............................................................................................................. 4
1.5 Herramientas computacionales ligadas con lenguajes ..................................................... 8
1.6 Estructura de un traductor ................................................................................................ 9
1.7 Fases de un compilador ..................................................................................................... 10
Conclusin .................................................................................................................................... 13
Referencias bibliogrficas ............................................................................................................ 14

Introduccin
En este trabajo de investigacin se darn a conocer los conceptos bsicos de lenguajes y autmatas.
As como tambin se hablar de la relevancia de conocer cada uno de ellos y la funcin de gran
importancia que desempean en la comunicacin hombre-mquina.
La teora de los lenguajes formales estudia unas entidades matemticas abstractas denominadas
lenguajes que en ningn momento debemos confundir o equiparar con las lenguas naturales. Sin
embargo, como veremos, los lenguajes formales pueden, en determinadas circunstancias, servirnos
como modelos abstractos de determinadas propiedades de las lenguas naturales, de ah la
importancia de conocer los fundamentos de la teora.
Un lenguaje formal (en adelante, simplemente lenguaje) es un conjunto, finito o infinito, de
cadenas definidas sobre un alfabeto finito.

1.1 Alfabeto
Un Alfabeto es un conjunto finito no vaco de smbolos. As, el alfabeto del idioma espaol: E = {a, b,
c, . . . , z}, es slo uno de tantos alfabetos posibles.
En general se utiliza la notacin

para representar un alfabeto. Con los smbolos de un alfabeto es

posible formar secuencias o cadenas de caracteres. Las cadenas de caracteres son llamadas tambin
palabras.
Un caso particular de cadena es la palabra vaca, , la cual no tiene ninguna letra.
La longitud de una palabra es la cantidad de letras que contiene, contando las repeticiones. Se
denota por |w| para una palabra w. Por ejemplo la palabra perro su longitud es 5.
Cuando escribimos varias palabras o caracteres uno a continuacin de otro, se supone que forman
una sola palabra (se concatenan).
La notacin usada para denotar la concatenacin de dos cadenas y es .
La concatenacin de palabras es asociativa esto es, (xy)z = x(yz), pero no conmutativa en el caso
general.
La longitud de una concatenacin cumple la propiedad: |uv| = |u| + |v|.
Una palabra v es subcadena de otra w cuando existen cadenas x, y - posiblemente vacas tales que
xvy = w.
El conjunto de todas las palabras que se pueden formar con un alfabeto es denotado
convencionalmente por .
Por ejemplo, si
= {a, b}
= {, a, aa, aaa, aaaa, . . . , b, bb, . . . , ab, aba, abb, . . .}
El conjunto es infinito, pero numerable.

1.2 Cadena
Una cadena o palabra es una serie arbitrariamente larga de smbolos unidos por concatenacin que
representamos disponiendo los diferentes smbolos que la componen en el orden deseado; por
ejemplo: aaabbbccc, es una cadena. Como la definicin de cadena es recursiva, podemos referirnos,
si es necesario, a una cadena completa o a una subcadena que forme parte de una cadena mayor
con las letras finales del alfabeto u, v, w, x, y y z. Por tanto, aaaw o, simplemente, w tambin son
cadenas. Denotamos la cadena vaca con el smbolo .

Cadena vaca
La cadena vaca es el elemento de identidad de la operacin de concatenacin, de tal modo que
aaabbb = aaabbb. La operacin de concatenacin de cadenas no es conmutativa (pero s
asociativa); por tanto aaabbb ab 6= ab aaabbb. La cadena vaca es aquella cadena que presenta
cero apariciones de smbolos. Esta cadena, designada por , es una cadena que puede construirse
en cualquier alfabeto.

Longitud de una cadena

Suele ser til clasificar las cadenas por su longitud, es decir, el nmero de posiciones ocupadas por
smbolos dentro de la cadena. Por ejemplo, 01101 tiene una longitud de 5. Es habitual decir que la
longitud de una cadena es igual al nmero de smbolos que contiene; esta proposicin est
aceptada coloquialmente, sin embargo, no es estrictamente correcta. As, en la cadena 01101 slo
hay dos smbolos, 0 y 1, aunque tiene cinco posiciones para los mismos y su longitus es igual a 5. Sin
embargo, generalmente podremos utilizar la expresin nmero de smbolos cuando realmente a
lo que se est haciendo referencia es al nmero de posiciones.
La notacin estndar para indicar la longitud de una cadena w es |w|. Por ejemplo, |011| = 3 y |
| = 0.

Concatenacin de cadenas
Sean x e y dos cadenas. Entonces, xy denota la concatenacin de x e y, es decir, la cadena formada
por una copia de x seguida de una copia de y. Dicho de manera ms precisa, si x es la cadena
compuesta por i smbolos x = a1a2 ai e y es la cadena compuesta por j smbolos y = b1b2 bj,
entonces xy es la cadena de longitud i+ j: xy = a1a2 aib1b2 bj.

1.3 Lenguajes
Un conjunto de cadenas, todas ellas seleccionadas de un , donde es un determinado alfabeto se
denomina lenguaje. Si es un alfabeto y L , entonces L es un lenguaje de . Observe que un
lenguaje de no necesita incluir cadenas con todos los smbolos de , ya que una vez que hemos
establecido que L es un lenguaje de , tambin sabemos que es un lenguaje de cualquier alfabeto
que sea un superconjunto de .
La eleccin del trmino lenguaje puede parecer extraa. Sin embargo, los lenguajes habituales
pueden interpretarse como conjuntos de cadenas. Un ejemplo sera el ingls, donde la coleccin de
las palabras correctas inglesas es un conjunto de cadenas del alfabeto que consta de todas las letras.
Otro ejemplo es el lenguaje C, o cualquier otro lenguaje de programacin, donde los programas
correctos son un subconjunto de las posibles cadenas que pueden formarse a partir del alfabeto del
lenguaje. Este alfabeto es un subconjunto de los caracteres ASCII. El alfabeto en concreto puede
diferir ligeramente entre diferentes lenguajes de programacin, aunque generalmente incluye las
letras maysculas y minsculas, los dgitos, los caracteres de puntuacin y los smbolos matemticos.
Sin embargo, existen tambin otros muchos lenguajes que veremos a lo largo del estudio de los
autmatas.

1.4 Tipos de lenguajes

Se crearon los lenguajes de bajo, medio y alto nivel, los cuales permitan al usuario escribir
instrucciones utilizando palabras claves o reservados. Y la diferencia entre ellos tanto del alto y el
bajo nivel es que el lenguaje se puede utilizar en una determinado computadora para el caso de bajo
nivel y la otra es capaz de ejecutarse en cualquier computadora para el caso de alto nivel.

Lenguaje mquina
Fue el primer lenguaje utilizado en la programacin para las primeras computadoras, pero dej de
utilizarse por su dificultad y complicacin, siendo sustituido por otros lenguajes ms fciles de
aprender y utilizar, y que adems reducen la posibilidad de cometer errores.
La informacin que hace que el
hardware de la computadora realice una
determinada
instruccin,

actividad
por

de

llama

consiguiente

una

instruccin es un conjunto de unos y

ceros, las instrucciones as formadas
equivalen a acciones elementales de la
mquina, por lo que al conjunto de
dichas

instrucciones

interpretadas

que

directamente

son
por

la

mquina se denomina lenguaje mquina.

El lenguaje mquina es el nico lenguaje que puede ejecutar una computadora, es especfico en cada
arquitectura, es un cdigo que es interpretado directamente por el microprocesador, est
compuesto por un conjunto de instrucciones ejecutadas en secuencia que representan acciones que
la mquina podr tomar.
El lenguaje mquina es el nico que entiende directamente la computadora, utiliza el alfabeto
binario que consta de los dos nicos smbolos 0 y 1, denominados bits; fsicamente, se materializan
con tensiones comprendidas entre 0 y 4.0 voltios y entre 4 y 5 voltios, respectivamente. Para
representar datos que contengan una informacin se utilizan una serie de unos y ceros cuyo
conjunto indica dicha informacin.

Lenguaje de bajo nivel

Los lenguajes de bajo nivel son ms fciles
de utilizar que los lenguajes mquina, pero,
al igual que ellos, dependen de la mquina
en particular. El lenguaje de bajo nivel por
excelencia

es

el

ensamblador.

Las

instrucciones en lenguaje ensamblador son

instrucciones

conocidas

como

nemotcnicos. Por ejemplo, nemotcnicos

tpicos de operaciones aritmticas son: en
ingls, ADD, SUB, DIV, etc.; en espaol,
SUM,RES,DIV,etc.
Un programa escrito en lenguaje ensamblador no puede ser ejecutado directamente por la
computadora en esto se diferencia esencialmente del lenguaje mquina, sino que requiere una fase
de traduccin al lenguaje mquina.
El programa original escrito en lenguaje ensamblador se denomina programa fuente y el programa
traducido en lenguaje mquina se conoce como programa objeto, ya directamente entendible por
la computadora.
El traductor de programas fuente a objeto es un programa llamado ensamblador, existente en casi
todos los computadores.

Lenguaje de mediano nivel

Lenguaje de medio nivel es un lenguaje de programacin informtica como el lenguaje C, que se
encuentran entre los lenguajes de alto nivel y los lenguajes de bajo nivel.
Suelen ser clasificados muchas veces de alto nivel, pero permiten ciertos manejos de bajo nivel. Son
precisos para ciertas aplicaciones como la creacin de sistemas operativos, ya que permiten un
manejo abstracto (independiente de la mquina, a diferencia del ensamblador), pero sin perder
mucho del poder y eficiencia que tienen los lenguajes de bajo nivel.

Una caracterstica distintiva, por ejemplo, que convierte a C en un lenguaje de medio nivel y al Pascal
en un lenguaje de alto nivel es que en el primero es posible manejar las letras como si fueran
nmeros (en Pascal no), y por el contrario en Pascal es posible concatenar las cadenas de caracteres
con el operador suma y copiarlas con la asignacin (en C es el usuario el responsable de llamar a las
funciones correspondientes).
Una de las caractersticas ms peculiares del lenguaje de
programacin C; es el uso de apuntadores, los cuales son
muy tiles en la implementacin de algoritmos como Listas
ligadas, Tablas Hash y algoritmos de bsqueda y
ordenamiento que para otros lenguajes de programacin
(como Java por ejemplo) les suele ser un poco ms
complicado implementar.

Lenguaje de alto nivel

El lenguaje de alto nivel (high-level language) es aquel que se aproxima ms al lenguaje natural
humano que al lenguaje binario de las computadoras, el que se conoce como lenguaje de bajo nivel.
Su funcin principal radica en que a partir de su desarrollo, existe la posibilidad de que se pueda
utilizar el mismo programa en distintas mquinas, es decir que es independiente de un hardware
determinado. La nica condicin es que la PC tenga un programa conocido como traductor o
compilador, que lo traduce al lenguaje especfico de cada mquina.
Y adems, al utilizar palabras del lenguaje humano (por lo general el ingls) es ms prctico y fcil
de manipular para el programador de manera que no corre tantos riesgos de equivocarse como si
es ms factible de caer en el error con el binario. De esta manera, el programador puede
concentrarse ms en el programa en s que en el lenguaje y, por otra parte, se reducen los tiempos
de creacin del programa, incluso en caso de que tenga que hacer modificaciones, son mucho ms
fciles de hacer.
Un punto en contra que tiene este tipo de lenguaje de tercera generacin es que en la actualidad
existe gran diversidad de ellos (PASCAL, BASIC, FORTRAN, C++, COBOL, ALGOL, entre muchos otros).

1.5 Herramientas computadoras ligadas con lenguajes.

Traductor.
Un traductor es un programa que tiene como entrada un texto escrito en un lenguaje (lenguaje
fuente) y como salida produce un texto escrito en un lenguaje (lenguaje objeto) que preserva el
significado de origen.
Ejemplos de traductores son los ensambladores y los compiladores.
Compilador.
El compilador es un programa informtico que traduce un programa escrito en lenguaje de
programacin y lo pasa a lenguaje de programacin, podemos decir que este programa nos permite
traducir un cdigo fuente de un programa en lenguaje de nivel alto, y lo pasmos a otro nivel inferior
(lenguaje maquina).

Ensambladores.
El ensamblador es el programa en que se realiza la traccin de un programa escrito en ensamblador
y lo pasa a lenguaje mquina. Directa o no directa la traduccin en que las instrucciones no son ms
que instrucciones que ejecuta la computadora.
Interpretes.
Los intrpretes son los que realizan normalmente dos operaciones:

Traducen el cdigo fuente a un formato interno.

Ejecuta o interpretan el programa traducido al formato interno.

Donde la primera pertenece al interprete el cual llama a veces al compilador, as se genera el cdigo
interno, pero no es el lenguaje de mquina, ni lenguaje de smbolos, ni mucho menos un lenguaje
de nivel alto.

1.6 Estructura de un traductor

Un traductor es un programa que tiene como entrada un texto escrito en un lenguaje (lenguaje
fuente) y como salida produce un texto escrito en un lenguaje (lenguaje objeto) que preserva el
significado de origen. Ejemplos de traductores son los ensambladores y los compiladores.

En el proceso de traduccin se identifican dos fases principales:

Fase de anlisis

Fase de Sntesis

1.7 Fases de un compilador

Un compilador es un programa que traduce un programa escrito en lenguaje fuente y produce otro
equivalente escrito en un lenguaje objetivo.
Estructura general de un compilador

Lenguaje fuente

Lenguaje de alto nivel. Por ejemplo: C, Pascal, C++.

Lenguaje especializado para alguna disciplina especfica dentro de las Ciencias de la

Computacin.

Salida

Cdigo de Mquina. Escrito en las instrucciones de mquina de la computadora en la que se

ejecutar.

Cdigo Binario. Deber ser vinculado con las libreras correspondientes para obtener el
cdigo ejecutable.

Cdigo Assembler. Deber ser ensamblado y vinculado.

Otro lenguaje de alto nivel.

10

Fases de un compilador

Anlisis lxico: lee la secuencia de caracteres de izquierda a derecha del programa fuente y agrupa
las secuencias de caracteres en unidades con significado propio (componentes lxicos o tokens en
ingls). Las palabras clave, identificadores, operadores, constantes numricas, signos de puntuacin
como separadores de sentencias, llaves, parntesis, etc., son diversas clasificaciones de
componentes lxicos.

11

Anlisis sintctico: determina si la secuencia de componentes lxicos sigue la sintaxis del lenguaje y
obtiene la estructura jerrquica del programa en forma de rbol, donde los nodos son las
construcciones de alto nivel del lenguaje. Se determinan las relaciones estructurales entre los
componentes lxicos, esto es semejante a realizar el anlisis gramatical sobre una frase en lenguaje
natural. La estructura sintctica la definiremos mediante las gramticas independientes del
contexto.
Anlisis semntico: realiza las comprobaciones necesarias sobre el rbol sintctico para determinar
el correcto significado del programa. Las tareas bsicas a realizar son: La verificacin e inferencia de
tipos en asignaciones y expresiones, la declaracin del tipo de variables y funciones antes de su uso,
el correcto uso de operadores, el mbito de las variables y la correcta llamada a funciones. El anlisis
semntico suele agregar atributos (como tipos de datos) a la estructura del rbol semntico.
Generacin y optimizacin de cdigo intermedio: la optimizacin consiste en la calibracin del rbol
sintctico donde ya no aparecen construcciones de alto nivel. Generando un cdigo mejorado, ya no
estructurado, ms fcil de traducir directamente a cdigo ensamblador o mquina, compuesto de
un cdigo de tres direcciones (cada instruccin tiene un operador, y la direccin de dos operndoos
y un lugar donde guardar el resultado), tambin conocida como cdigo intermedio.
Generacin de cdigo objeto: toma como entrada la representacin intermedia y genera el cdigo
objeto. La optimizacin depende de la mquina, es necesario conocer el conjunto de instrucciones,
la representacin de los datos (nmero de bytes), modos de direccionamiento, nmero y propsito
de registros, jerarqua de memoria, encauzamientos, etc. Suelen implementarse a mano, y son
complejos porque la generacin de un buen cdigo objeto requiere la consideracin de muchos
casos particulares.
Tabla de smbolos: es una estructura tipo diccionario con operaciones de insercin, borrado y
bsqueda, que almacena informacin sobre los smbolos que van apareciendo a lo largo del
programa como son: los identificadores (variables y funciones) Etiquetas tipos definidos por el
usuario (arreglos, registros, etc.).
Gestor de errores: Detecta e informa de errores que se produzcan durante la fase de anlisis. Debe
generar mensajes significativos y reanudar la traduccin.

12

Conclusin
Es muy importante conocer los conceptos bsicos sobre lenguajes y autmatas. Adems de explicar
detalladamente los tipos de lenguajes y mencionar algunos ejemplos para que pudiera
comprenderse mucho mejor cada uno.
Tambin se aclararon algunos puntos importantes sobre las herramientas computacionales que
intervienen en la comunicacin hombre-mquina, como lo son; compilador, intrprete, traductor y
ensamblador.
Pudimos comprender la estructura de un traductor as como tambin, las fases de un compilador y
las funciones que desarrollan durante la transmisin de mensajes entre la mquina y el hombre.

13

Referencias bibliogrficas

Hopcroft John E., Introduccin a la Teora de Autmatas, Lenguajes y Computacin, 2da ed, Ed.
Addison Wesley, 2004.
Balari, S. (2014). Cap. 1: Nociones bsicas. En Teora de lenguajes formales (pp.9-13). Barcelona,
Espaa: Centro de Lingstica Terica.
Villalta, P. (2012). Introduccin a Compiladores e Intrpretes. 2016, de Blogspot Sitio web:
http://compiladores-interpretes.blogspot.mx/2012/01/introduccion-compiladores-einterpretes.html
Jos, A. (diciembre 17, 2013). Lenguaje Compilado e interpretado. 2016, de Ciencia&Educacin Sitio
web: http://cienciaeducacion502.blogspot.mx/2013/12/lenguaje-compilado-e-interpretado.html

14