Introducción A La Teoría De Lenguajes Formales

INSTITUTO TECNOLOGICO DE TEPIC
LENGUAJES Y AUTOMATAS
INGENIERIA EN SISTEMAS COMPUTACIONALES
FECHA 18 DE FEBRERO DEL 2013
INSTITUTO TECNOLOGICO DE TEPIC
LENGUAJES Y AUTOMATAS
INGENIERIA EN SISTEMAS COMPUTACIONALES
FECHA 18 DE FEBRERO DEL 2013

INSTITUTO TECNOLOGICO DE TEPIC
PORTAFOLIO
UNIDAD 1
“INTRODUCCIÓN A LA TEORÍA DE LENGUAJES FORMALES”



1.1 ALFABETO
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 unalfabeto 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 ensu 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
Cadena: 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 diceque 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 yalfabeto. 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
Lenguajes: La definición de lenguajes la encontré de diferentes autores y cada uno usa sus términos comoJonh 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 lenguajeshabituales 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 unlenguaje 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 yfuncionalidad 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...