control de lectura_capitulo 2 - Mauricio axel 20

Vista previa del material en texto

Lenguajes y autómatas 1 
INSTITUTO TECNOLÓGICO NACIONAL DE MÉXICO
INSTITUTO TECNOLÓGICO DE ACAPULCO
Ingeniería en sistemas computacionales
Lenguajes y autómatas 1
Control de lectura 
2.Autómatas finitos
Profesor: Bedolla Solano Silvestre
López Anselmo Mauricio Axel 
CONTROL: 18320904
2.-Autómatas finitos
Ideas principales.
· Describir los lenguajes regulares
· Identificar los autómatas finitos deterministas y no deterministas y sus lenguajes
 Resumen.
“lenguajes regulares”. Estos lenguajes son aquellos que pueden describirse mediante un autómata finito. Un autómata finito tiene un conjunto de estados y su “control “pasa de un estado a otro en respuesta a las “entradas” externas. Una de las diferencias fundamentales entre las clases de autómatas finitos es si dicho control es “determinista”, lo que quiere decir que el autómata no puede encontrarse en más de un estado a un mismo tiempo, o “no determinista”, lo que significa que sí puede estar en varios estados a la vez. 
ejemplo extendido de un problema real, cuya solución emplea autómatas finitos que desempeñan un importante papel.
Se investigarán protocolos para gestionar dinero electrónico. ejemplo extendido de un problema real, cuya solución emplea autómatas finitos que desempeñan un importante papel. cuestión de la falsificación del archivo es algo que un banco debe asegurar mediante una política criptográfica. Es decir, un tercer jugador, el banco, tiene que emitir y cifrar los archivos de “dinero”, de manera que la falsificación no constituya un problema. Sin embargo, el banco desempeña una segunda tarea también importante: tiene que mantener una base de datos de todas las transacciones válidas que se hayan realizado, de modo que sea posible verificar al vendedor que el archivo que ha recibido representa dinero real que ha sido ingresado en su cuenta.
tenemos tres participantes: el cliente, la tienda y el banco.
 El cliente puede decidir transferir este archivo a la tienda, la cual lo reenviar al banco (es decir, solicita al banco que emita un nuevo archivo que refleje que el dinero pertenece a la tienda en lugar de al cliente) y suministra los bienes al cliente. Además, el cliente tiene la opción de cancelar el archivo; es decir, el cliente puede pedir al banco que devuelva el dinero a su cuenta, anulando la posibilidad de gastarlo.
 La interacción entre los tres participantes se limita por tanto a cinco sucesos:
1. El cliente decide pagar. Es decir, el cliente envía el dinero a la tienda.
2. El cliente decide cancelar el pago. El dinero se envía al banco con un mensaje que indica que el dinero se ha añadido a la cuenta bancaria del cliente.
3. La tienda suministra los bienes al cliente.
4. La tienda libra el dinero. Es decir, el dinero se envía al banco con la solicitud de que su valor se asigne ala cuenta de la tienda.
5. El banco transfiere el dinero creando un nuevo archivo de dinero electrónico cifrado y se lo envía a la tienda. 
Síntesis
Los lenguajes regulares son aquellos que pueden describirse como un autómata finito. Un autómata finito tiene un conjunto de estados y su control pasa de un estado a otro.
Hay autómatas deterministas y no deterministas, los deterministas no se pueden encontrar en mas de un estado y los no deterministas si pueden encontrarse en más de un estado.
La forma normal de explorar la interacción de autómatas consiste en crear el autómata producto. 
Ahora el autómata finito determinista hace referencia que para cada entrada solo existe uno y solo un estado por el cual puede hacer la transición a partir de su estado.
Este autómata consta de:
1.- un conjunto finito de estados.
2.- un conjunto finito de símbolos de entrada.
3.- Una función de transición que toma como argumentos un estado y un símbolo de entrada y devuelve un estado. La función de transición se designa habitualmente como δ.
4.- un estado inicial 
5.- un conjunto de estados finales o de aceptación
El “lenguaje” del AFD es el conjunto de todas las cadenas que acepta.
Un autómata finito “no determinista” como se dice, este puede estar en varios estados, esta capacidad a me nudo expresa como la posibilidad de que el autómata conjeture algo acerca de su entrada, por ejemplo, cuando este busca una secuencia de caracteres (palabras clave). 
Al igual que el AFD, un AFN tiene un conjunto finito de estados, un conjunto finito de símbolos de entrada, un estado inicial y un conjunto de estados de aceptación.
La diferencia entre los AFD y los AFN se encuentra en el tipo de función δ. En los AFN, δ es una función que toma un estado y símbolos de entrada como argumentos (al igual que la función de transición del AFD), pero devuelve un conjunto de cero, uno o más estados (en lugar de devolver exactamente un estado, como lo hacen los AFD). 
Bibliografías.
· Libro base-teoría de autómatas, lenguajes y computación-hopcroft
Página 1 | 1
Acapulco Gro. 25 de septiembre de 2020