Monografia matematicas discretas automatas

INGENIERÍA DE SISTEMAS
ESTRUCTURAS DISCRETAS II

ENERO - 2011

INDICE
INTRODUCCION………………………………………………………………………………………………………..2
CAPITULO 1
INTRODUCCION A AUTOMATAS…………………………………………………………………………….3
Autómata Finito………………………………………………………………………………………………………3
Autómata Finito no Determinista ………………………………………………………………………..7
Autómata de pila ………………………………………………………………………………………………..10
CAPITULO 2INTRODUCCION A LENGUAJES Y GRAMATICAS…………………………………………………..12
1. Definición de lenguajes: …………………………………………………………………………..12
2. Definición de gramática: ………………………………………………………………………….13

CAPITULO 3
APLICACIONES DE LENGUAJES, GRAMATICAS Y AUTOMATAS………………………..….15
1. Construcción de compiladores………………………………………………………………………….15
2. Análisis del lenguaje natural:………………………………………………………………………....16
3. Problemas con análisis de cadenas de caracteres: …………………………………………19
4. Programación Lógica………………………………………………………………………………………...19
5. Editores de texto: …………………………………………………………………………………………..…20
6. En la Biología de Sistemas: …………………………………………………………………………..…20
7. Aplicaciones en Hardware: ………………………………………………………………………………21
8. Los autómatas celulares…………………………………………………………………………………..229. Aplicación de autómatas en la robótica………………………………………………………..…23
10. Un Lenguaje Para La Especificación de Autómatas Celulares con Aplicación en Biología……………………………………………………………………………………………………………..23
AUTÓMATAS CELULARES (AC)………………………………………………………………………..…….24
Descripción formal del lenguaje de autómatas celulares – FORTH(ACF)……………24
El autómata celular deACF…………………………………………………………………………………..25
Autómatas celulares - FORTH para Windows(ACFw)……………………………………….…25
11. Aplicaciones Biológicas………………………………………………………………………………….26
Crecimiento de cáncer ………………………………………………………………………………………….27
Crecimiento de población con limitaciones de recursos………………………………………31
CONCLUSIONES
BIBLIOGRAFIA

INTRODUCCION
En el presente trabajo tratamos acerca de los autómatas, lenguajes y gramáticas, asi como las diferentes aplicaciones que tienen, de esa formaveremos lo importante que es para nuestra carrera este tema, y nos ayudara a entender mejor el funcionamiento de nuestro trabajo como ingenieros de sistemas.
Para comenzar como bien sabemos nosotros como seres humanos tenemos un lenguaje que nos permite comunicarnos entre nosotros mismos, que nos ayuda a entendernos cuando transmitimos nuestras ideas, y para poder transmitirlas se sigue unconjunto de reglas, para poder decir oraciones con sentido y significado.
Para poder comunicarnos entre nosotros utilizamos los diferentes lenguajes naturales que existen y para poder comunicarnos con las maquinas utilizamos lenguajes artificiales a través de un conjunto de símbolos.
Entonces podemos decir que un lenguaje es un conjunto de palabras también llamadas cadenas o sentencias, que estánformadas por símbolos de un alfabeto. Una gramática da cuenta de la estructura del lenguaje, es decir de las sentencias que lo forman, proporcionando las formas validas en que se puede combinar los símbolos del alfabeto.
También debemos de mencionar que los lenguajes formales (lenguajes de programación) obedecen a reglas preestablecidas y por tanto se ajustan a ellas, no evolucionan y han sidocreados para un fin específico. Sin embargo los lenguajes naturales usados por el hombre existen por si y las reglas gramaticales que rigen su estructura han sido desarrolladas con posterioridad para explicar esta ultima.
Una maquina abstracta o autómata es un dispositivo teórico capaz de recibir y transmitir información. Para realizar esta labor manipula cadenas de símbolos que se le presenta ala entrada produciendo otras tiras o cadenas de símbolos a su salida mediante un conjunto de estados que contienen la información necesarios para poder deducir, dado un símbolo de entrada, cual será el símbolo de salida en cada momento.
Equivale
Maquina
Gramática

Describe, genera
Reconoce, genera...