Unidad I: Introducción a la Teoría de Lenguajes Formales

1.1 Alfabeto 

Leyendo sobre varios autores para comprender la definición de alfabeto puedo decir claramente que Deán Kelly en su libro “Teoría de autómatas y lenguajes formales” nos dice que un alfabeto “Es un conjunto no vacío y finito de símbolos” por otro lado Jonh E. Hpocroft, Rajeev Motwani y Jeffrey D. Ullman en su libro “Introducción a la teoría de autómatas, Lenguajes y Computación” nos definen que un alfabeto es un conjunto finito no vacio de símbolos, sin embargo Otros autores como Pedro García, Tomás Pérez, José Ruíz, Encarna Segarra, José M. Sempere y M. Vázquez de Parga nos dicen en su libro “Teoría de autómatas y lenguajes formales” que un alfabeto es cualquier conjunto finito y no vacío de elementos que denominan símbolos y los denotaran con el símbolo Ʃ. Con otro autor como John Martin en su libro “Lenguajes formales y teoría de la computación” Por tanto puedo concluir que un alfabeto es un conjunto no vacío y finito de símbolos denotado por el símbolo Ʃ. 

1.2 Cadenas

La definición de cadena se puede encontrar con varias definiciones como Deán Kelly en su libro “Teoría de autómatas y lenguajes formales” nos dice que en su libro definirá cadena como palabra y dice que una secuencia finita de símbolos de un determinado alfabeto es conocido como palabra ó cadena. Por otro lado John Martin en su libro “Lenguajes formales y teoría de la computación” define como cadena en un alfabeto Ʃ se obtiene al ordenar elementos de Ʃ (o posiblemente ninguno) este autor no define la palabra cadena en sí pero si la utiliza mucho en sus definiciones para lenguajes y alfabeto. Otra definición de Jonh E. Hpocroft, Rajeev Motwani y Jeffrey D. Ullman en su libro “Introducción a la teoría de autómatas, Lenguajes y Computación” nos dicen que una cadena (también llamada palabra) es una secuencia finita de símbolos pertenecientes a un alfabeto. 

1.3 Lenguajes 

La definición de lenguajes la encontré de diferentes autores y cada uno usa sus términos como Jonh E. Hpocroft, Rajeev Motwani y Jeffrey D. Ullman en su libro “Introducción a la teoría de autómatas, Lenguajes y Computación” nos dice que un lenguaje es un conjunto de cadenas, todas ellas elegidas de algún Ʃ*donde Ʃ es un alfabeto, algo que me llamo la atención de este libro es que los autores comentan que la definición de Lenguajes puede parecer extraña más sin embargo los lenguajes habituales se pueden considerar como conjuntos de cadenas. Otro autor como John Martin en su libro “Lenguajes formales y teoría de la computación” define lenguajes como que es simplemente un conjunto de cadenas que incluyen símbolos de un alfabeto. Por tanto Lenguajes: La definición de lenguajes la encontré de diferentes autores y cada uno usa sus términos como Jonh E. Hpocroft, Rajeev Motwani y Jeffrey D. Ullman en su libro “Introducción a la teoría de autómatas, Lenguajes y Computación” nos dice que un lenguaje es un conjunto de cadenas, todas ellas elegidas de algún Ʃ*donde Ʃ es un alfabeto, algo que me llamo la atención de este libro es que los autores comentan que la definición de Lenguajes puede parecer extraña más sin embargo los lenguajes habituales se pueden considerar como conjuntos de cadenas. Otro autor como John Martin en su libro “Lenguajes formales y teoría de la computación” define lenguajes como que es simplemente un conjunto de cadenas que incluyen símbolos de un alfabeto. Por tanto puedo concluir que un alfabeto es un conjunto no vacío y finito de símbolos denotado por el símbolo Ʃ. Sin embargo Deán Kelly nos dice que un lenguaje es un conjunto de palabras o de cadenas y se puede tener el lenguaje compuesto por ninguna cadena. 

1.4 Tipos de lenguajes 

Podemos encontrar varios tipos de lenguajes: 

 Lenguajes declarativos 

 Lenguajes de alto nivel

 Lenguajes ensambladores 

 Lenguajes máquina 

Los lenguajes declarativos son los más parecidos al castellano o inglés en su potencia expresiva y funcionalidad y están en el nivel más alto respecto a los otros. Son fundamentalmente lenguajes de órdenes, dominados por sentencias que expresan “lo que hay que hacer” en vez de “cómo hacerlo”. Los lenguajes de alto nivel son los más utilizados como lenguajes de programación Aunque no son fundamentalmente declarativos, estos lenguajes permiten que los algoritmos se expresen en un nivel y estilo de escritura fácilmente legible y comprensible por otros programadores. Además, los lenguajes de alto nivel suelen tener la característica de “transportabilidad”. 

1.5 Herramientas computacionales ligadas con lenguajes 

Editores de estructuras: “Un editor de estructuras toma como entrada una secuencia de órdenes para construir un programa fuente. El editor de estructuras no sólo realiza las funciones de creación y modificación de textos de un editor de textos ordinario, sino que también analiza el texto del programa, imponiendo al programa fuente una estructura jerárquica apropiada. De esa manera, el editor de estructuras puede realizar tareas adicionales útiles para la preparación de programas” Concepto encontrado en el libro de Compiladores de Addison Wesley, a mi punto de vista estos editores de estructura son los que se encarga de llevar el orden de las palabras, valla el acomodo y comprobar si la entrada está formada correctamente. Impresoras estéticas: “Una impresora estética analiza un programa y lo imprime de forma que la estructura del programa resulte claramente visible” Concepto encontrado en el libro de Compiladores de Addison Wesley. Verificadores estáticos: Este verificador lee un programa, lo analiza e intenta descubrir errores potenciales sin correr el programa, algo muy parecido a la corrección de los editores de texto como Word. “Un verificador estático puede detectar si hay partes de un programa que nunca se podrán ejecutar o si cierta variable se usa antes de ser definida” nos dice Addison Wesley. Intérpretes: “En lugar de producir un programa objeto como resultado de una traducción, un intérprete realiza las operaciones que implica el programa fuente. Muchas veces los interpretes se usan para ejecutar lenguajes de órdenes, pues cada operador que se ejecuta en un lenguaje de ordenes suele ser una invocación de una rutina compleja, como un editor o un compilador”. 

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. 

1.7 Fases de un compilador 

 Fase de análisis 

 Fase de Síntesis