ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

Teoría de lenguajes formales para la materia de Lenguajes y Autómatas I de la carrera de ISC


Enviado por   •  10 de Septiembre de 2015  •  Ensayo  •  1.256 Palabras (6 Páginas)  •  334 Visitas

Página 1 de 6

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.

...

Descargar como (para miembros actualizados) txt (9 Kb) pdf (436 Kb) docx (160 Kb)
Leer 5 páginas más »
Disponible sólo en Clubensayos.com