control de lectura_capitulo 1 - Mauricio axel 20

Vista previa del material en texto

INSTITUTO TECNOLÓGICO NACIONAL DE MÉXICO
INSTITUTO TECNOLÓGICO DE ACAPULCO
Ingeniería en sistemas computacionales
Lenguajes y autómatas 1
Introducción a los autómatas
Profesor: Bedolla Solano Silvestre
López Anselmo Mauricio Axel 
CONTROL: 18320904
Introducción a los autómatas finitos.
Ideas principales.
· Comprensión de la teoría de autómatas.
· Entendimiento de las demostraciones 
· Estudio de los conceptos de la teoría de autómatas.
 Resumen.
La teoría de autómatas es el estudio de dispositivos de cálculo abstractos, es decir, de las “máquinas”.
En la década de los años treinta, A. Turing estudió una máquina abstracta que tenía todas las capacidades de las computadoras de hoy día, al menos en lo que respecta a lo que podían calcular. El objetivo de Turing era describir de forma precisa los límites entre lo que una máquina de cálculo podía y no podía hacer; estas conclusiones no sólo se aplican a las máquinas abstractas de Turing, sino a todas las máquinas reales actuales.
Los autómatas finitos constituyen un modelo útil para muchos tipos de hardware y software.
1. Software para diseñar y probar el comportamiento de circuitos digitales.
2. El “analizador léxico” de un compilador típico, es decir, el componente del compilador que separa el texto de entrada en unidades lógicas, tal como identificadores, palabras clave y signos de puntuación.
3. Software para explorar cuerpos de texto largos, como colecciones de páginas web, o para determinar el número de apariciones de palabras, frases u otros patrones.
4. Software para verificar sistemas de todo tipo que tengan un número finito de estados diferentes, tales como protocolos de comunicaciones o protocolos para el intercambio seguro de información.
EJEMPLO 1.1Quizá el autómata finito no trivial más simple sea un interruptor de apagado/encendido (posiciones on/off). El dispositivo recuerda si está en el estado encendido (“on”) o en el estado apagado (“off”), y permite al usuario pulsar un botón cuyo efecto es diferente dependiendo del estado del interruptor. Es decir, si el interruptor está en el estado off, entonces al pulsar el botón cambia al estado on, y si el interruptor está en el estado on, al pulsarle mismo botón pasa al estado off.
Síntesis
La teoría de autómatas nos indica que es el estudio de las “maquinas”, esta teoría se propuso para modelar el funcionamiento del cerebro, pero resultaron útiles para otros propósitos, N. Chomsky realizo el estudio de las gramáticas formales, aunque no son estrictamente maquinas están muy relacionadas con los autómatas y sirven como base para varios componentes de software como son los compiladores.
Los autómatas finitos crean un modelo para muchos tipos de hardware y software que sirven para diseñar y probar los circuitos digitales, explorar textos largos como lo son de páginas web, detectar cuantas veces se repite una frase y diferentes patrones de texto.
Estos autómatas finitos podríamos implementarlos por hardware o como un simple programa que pueda tomar decisiones consultando datos por ejemplo un interruptor de encendido y apagado.
Existen dos anotaciones que no se utilizan con regularidad con los autómatas, pero son necesarios para su estudio, las gramáticas y las expresiones regulares.
Las gramáticas son útiles para el diseño de software que sirve para procesar datos y las expresiones regulares especifican la estructura de los datos, principalmente en las cadenas de texto.
Como se ha visto los autómatas son esenciales para el estudio de la computación, de los cuales existen dos factores. La decidibilidad y la intratabilidad.
La decidibilidad nos dice que existe un algoritmo para cada formula del sistema que es capaza de decidir en un numero finito de pasos si la formula es valida o no en el sistema.
La intratabilidad nos dice que una computadora puede resolver en un tiempo proporcional alguna función que crezca lentamente con la entrada se dice que son “tratables”.
Otros conceptos fundamentales de la teoría de autómatas son:
Alfabetos: son el conjunto de símbolos finitos y no vacíos el cual se designa con el símbolo Σ. Entre los alfabetos más comunes están, el alfabeto binario, el conjunto de todas las letras minúsculas, el código ASCII, entre otros.
Conjunto de caracteres(palabra): es una secuencia finita de símbolos que son seleccionados de un alfabeto: por ejemplo, 01101 que es una cadena del alfabeto binario.
Cadena vacía: es aquella que no presenta símbolos y es designada por el símbolo ε y puede crearse en cualquier alfabeto.
Longitud de una cadena: algunas veces resulta útil clasificar las cadenas por su longitud, o sea el numero de posiciones ocupadas por símbolos en la cadena.
Los lenguajes son un conjunto de cadenas, un ejemplo sería los lenguajes de programación donde los programas son un subconjunto de cadenas que pueden formarse a partir del alfabeto del lenguaje.
Bibliografías.
· libro base-teoría de autómatas, lenguajes y computacion-hopcroft.
· https://sites.google.com/site/tautomatasfinal/decidibilidad
Página 1 | 1
Acapulco Gro. 18 de septiembre de 2020