Teoría de lenguajes formales para la materia de Lenguajes y Autómatas I de la carrera de ISC
Enviado por Saúl Meneses • 10 de Septiembre de 2015 • Ensayo • 1.256 Palabras (6 Páginas) • 333 Visitas
INSTITUTO TECNOLÓGICO DE HERMOSILLO
[pic 1]
Teoría de lenguajes formales para la materia de Lenguajes y Autómatas I de la carrera de ISC
Maestra: MC ANA LUISA MILLAN CASTRO
Alumno: Saúl Alejandro Meneses Alaniz
Num de control: 12330519
Contenido
Introducción 3
Alfabeto 3
Cadena 4
Subcadena 4
Cadena vacía 4
Longitud de cadena 4
Clausura de Kleene 5
Autores y Línea del tiempo 5
Traductor 6
Tipos de traductores 7
Intérprete 7
Ensambladores 8
Preprocesadores 8
Compilador 8
Fases de un compilador 9
Bibliografía 10
Introducción
Los lenguajes formales estudian entidades abstractas denominadas “Lenguajes”. Para conocer un lenguaje, primero hay que saber cómo está compuesto.
Un lenguaje formal es un conjunto finito o infinito de cadenas provenientes de un alfabeto fijo.
La teoría de los lenguajes formales estudia los lenguajes prestando atención únicamente a sus propiedades estructurales, definiendo clases de complejidad estructural y estableciendo relaciones entre las diferentes clases.
Un lenguaje está compuesto por un conjunto finito o infinito de cadenas de un alfabeto fijo.
[pic 2]
Alfabeto
Se conoce como alfabeto a un conjunto finito, no vacío, cuyos elementos se denominan como “letras” o “símbolos”. Se definen por la enumeración de símbolos que contienen.
“Es un conjunto no vacío y finito de símbolos”
-Dean Kelly
“Un alfabeto es un conjunto de símbolos finito y no vacío.”
-Jonh E. Hopcroft, Rajeev Motwani y Jeffrey D. Ullman
“Un alfabeto es un conjunto finito de símbolos.”
-Sergio Balari
Generalmente se utiliza ∑ para indicar un alfabeto.
Ejemplo:
∑={a,b,c}
Cadena
Las cadenas o palabras, es una secuencia finita arbitrariamente larga de símbolos unidos por concatenación. Se representan con los diferentes símbolos de un alfabeto fijo que la componen en el orden deseado.
“Es una secuencia finita de símbolos pertenecientes a un alfabeto.”
- Jonh E. Hopcroft, Rajeev Motwani y Jeffrey D. Ullman
Ejemplo:
∑={a,b,c}
{a, b, c, abc, aab, …}
Subcadena
Como la definición de cadena es recursiva, puede referirse tanto a una cadena como a una subcadena.
Una subcadena forma parte de una cadena mayor, eliminando un prefijo y un sufijo de la misma.
Cadena vacía
La cadena vacía es el elemento de longitud cero. Se representa con ϵ
Longitud de cadena
Se puede obtener la longitud de una cadena midiendo la cantidad de símbolos que la componen.
Ejemplo:
│abc│= 3
Clausura de Kleene
La clausura o cerradura de Kleene es una operación unaria que se aplica sobre un conjunto de cadenas. Un lenguaje A, donde A pertenece a un alfabeto ∑, es la unión de todas las potencias de A y se denota por A*.
Ejemplo:
∑={a}
A ⊆ ∑={a}
A*=={ϵ, a, aa, aaa, …}[pic 3]
Autores y Línea del tiempo
Autores | Aplicaciones |
Friedrich Gottlob Frege | 1879 - Publicó la Conceptografía y desarrollo la lógica de los operadores (and, or, not). |
Giuseppe Peano | 1884 – Publicó su primer libro sobre lógica matemática (usa símbolos modernos para la unión e intersección de conjuntos). |
Bertrand Rusell y Alfred Whitehead | 1910, 1912, 1913 - Publicaron “Principia Mathematica”(es un intento de derivar los conocimientos matemáticos de esa época, tomando algunos principios y axiomas). |
David Hilbert | 1900 – Da a conocer el programa Hilbert (Fundamentos de la geometría en ese entonces). Buscaba establecer las matemáticas en un sistema axiomático. Un sistema que iba a hacer axiomas mucho más completos y abstractos. Un axioma es una consideración que se acepta sin demostración. 1928 – Publicó “Principios de lógica teórica”. 1931 – Aportación a la metamatemática. |
Kurt Gödel | 1931 – Teoremas de incompletitud. El primer teorema habla acerca de cómo ninguna teoría matemática es capaz de describir los números naturales y la aritmética. Son uno de los grandes avances de la lógica matemática. |
Alan Turing | 1936 – Publicó “Los números computables, con una aplicación al Entscheidungsproblem” 1937 – Publicó un artículo en donde se dio a conocer “la máquina de Turing”. Diseñó un método para deducir si una máquina era capaz de pensar como un hombre (Test de Turing). |
Alonzo Church y Stephen Kleene | 1930 - Su obra más conocida fue el desarrollo del cálculo lambda. Es un sistema diseñado para investigar la definición de función (un subalgoritmo que forma parte de un algoritmo principal). En 1936 se usó para resolver el Entscheidungsproblem (problema de decisión). |
Alonzo Church y Alan Turing | En 1936 se demostró que el cálculo de lambda y la máquina de Turing tenían el mismo poder de expresión, como resultado se postuló la tesis Church-Turing. |
Noam Chomsky | 1955 – Publica “Estructuras sintácticas”, en el que aparece la clasificación de gramáticas (Jerarquía Chomsky). Es una clasificación de distintos tipos de gramáticas formales. La jerarquía consta de 4 niveles. |
...