Page 5 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

5

ENTREGA I

CONCEPTOS PRELIMINARES

Lenguajes formales: para abordar una definición formal de lenguajes formales,
empecemos por precisar ¿qué es un lenguaje?, un lenguaje es un conjunto de palabras y
oraciones o sentencias formadas sobre un alfabeto y para ese lenguaje cada palabra y
sentencia u oración tiene que tener asociada una sintaxis y una semántica, que expresen lo
que se puede y cómo se puede utilizar. Preliminarmente podemos definir lenguaje formal
como: conjunto compuesto por cadenas de longitud finita formadas por símbolos tomados
de un mismo alfabeto. Queda pendiente consignar una definición más apropiada para este
concepto en el contexto de informática y autómatas, en donde hay que explorar
definiciones y precisiones respecto a: palabra, cadenas, frases, sentencias, alfabeto,
lenguaje, etc.

Autómatas: preliminarmente un autómata son máquinas o dispositivos abstractos con
capacidad de computación. Ahora bien, ¿qué tiene que ver los lenguajes formales con los
autómatas? La teoría de autómatas está estrechamente relacionada con la teoría del
lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes
formales que son capaces de reconocer. Un autómata es un modelo matemático para una
máquina de estado finita, la cual es una máquina que, dada una entrada de símbolos,
"transita" a través de una serie de estados de acuerdo con una función de transición (que
puede ser expresada como una tabla). Esta función de transición dice al autómata a qué
estado cambiar dados unos determinados estados y símbolos. La entrada es leída símbolo
por símbolo, hasta que es "consumida" completamente. Una vez que la entrada se ha
agotado, el autómata se detiene. Dependiendo del estado en el que el autómata para, se
dice que este ha aceptado o rechazado la entrada, el conjunto de todas las palabras
aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.

Compiladores: son programas de computadoras que traducen un lenguaje a otro. Un
compilador toma como entrada un programa escrito en su lenguaje fuente y produce un
programa equivalente escrito en código objeto, también llamado código de máquina.
Recuérdese que el código de máquina se refiere a las instrucciones correspondientes al
lenguaje fuente escrito, ahora en las instrucciones de máquina correspondientes a la
computadora en la cual se ejecutará (¡de allí el problema de portabilidad!). ¿Qué tiene que
ver los compiladores con los autómatas y los lenguajes formales? Los compiladores son
programas complejos con muchas líneas de código (varían de 10,000 a 1000,000) por
consiguiente esta es tarea difícil tanto comprenderlo como escribirlo. Las técnicas y teoría
de autómatas hacen de la construcción de compiladores una tarea más manejable.
Entonces vislumbramos como estos conocimientos se enlazan y complementan y en
consecuencia la presencia de estos temas.