Actividad_3 4 y 3 5_lenguajes y automatas - Mauricio axel 20

Vista previa del material en texto

3.4 Minimización de estados en un autómata Finito.
Minimización de un AFD 
Dos estados de un autómata finito determinista son estados equivalentes si al unirse en un sólo estado, pueden reconocer el mismo lenguaje regular que si estuviesen separados. Esta unión de estados implica la unión tanto de sus transiciones de entrada como de salida. Si dos estados no son equivalentes, se dice que son estados distinguibles. Un estado final con un estado no-final nunca serán equivalentes.
Un AFD está minimizado, si todos sus estados son distinguibles y alcanzables. Un algoritmo de minimización de AFD es el siguiente:
Eliminar los estados inaccesibles del autómata.
Construir una tabla con todos los pares (p, q) de estados restantes.
Marcar en la tabla aquellas entradas donde un estado es final y el otro es no-final, es decir, aquellos pares de estados que son claramente distinguibles.
Para cada par (p, q) y cada símbolo a del alfabeto, tal que r = δ(p,a) y s = δ(q,a):
Si (r, s) ya ha sido marcado, entonces p y q también son distinguibles, por lo tanto, marcar la entrada (p, q).
De lo contrario, colocar (p, q) en una lista asociada a la entrada (r, s).
Agrupar los pares de estados no marcados.
Luego del tercer paso, si la tabla creada queda completamente marcada, entonces el AFD inicial ya era mínimo.
se muestra un autómata con el estado inaccesible d, el cual puede eliminarse inmediatamente. Luego se construye la tabla de pares de estados, y a continuación se marcan, de acuerdo a la tercera línea del algoritmo, las filas y columnas correspondientes a los estados finales c y g, salvo la celda que representa el par (c,g), puesto que al ser ambos estados finales, pueden ser estados equivalentes. Posteriormente, se marcan las celdas restantes de acuerdo a la cuarta línea del algoritmo, notando que el par (b, f) queda asociado con el par (c, g), y así finalmente se obtiene el autómata final, agrupando los estados b y f, así como c y g.
3.5 Aplicaciones de un autómata finito.
APLICACION DE LOS AUTOMATAS A LINGÜÍSTICACOMPUTACIONAL
 COMPILADOR
Un compilador es un programa informático que traduce un programa escrito en un lenguaje de programación a otro lenguaje de programación, generando un programa equivalente que la máquina será capaz de interpretar. Usualmente el segundo lenguaje es código máquina, pero también puede ser simplemente texto. Este proceso de traducción se Conoce como compilación. 
APLICACIÓN DE LOS AUTOMATAS PARA EL DESARROLLO DE UNA RED NEURONAL ARTIFICIAL
Las redes de neuronas artificiales (denominadas habitualmente como RNA o en inglés como: "ANN"1) son un paradigma de aprendizaje y procesamiento automático inspirado en la forma en que funciona el sistema nervioso de los animales. Se trata de un sistema de interconexión de neuronas en una red que colabora para producir un estímulo de salida. En inteligencia artificial es frecuente referirse a ellas como redes de neuronas o redes neuronales.
APLICACIÓN DE LOS AUTOMATAS FINITOS EN LA INDUSTRIA
1. AUTOMÓVIL
Cadenas de montaje, soldadura, cabinas de pintura, transmisiones. Máquinas herramientas: Tornos, fresadoras, taladradoras, etc.
2. PLANTAS QUÍMICAS Y PETROQUÍMICAS
Control de procesos (dosificación, mezcla, pesaje, etc).Baños electrolíticos, oleoductos, refinado, tratamiento de aguas residuales, etc.
3. METALURGIA
Control de hornos, laminado, fundición, soldadura, forja, grúas, entre otros.
4. ALIMENTACIÓN
Envasado, empaquetado, embotellado, almacenaje, llenado de botellas, etc.
5. PAPELERAS Y MADERERAS
Control de procesos, serradoras, producción de conglomerados y de laminados, etc.
6. PRODUCCIÓN DE ENERGÍA
Centrales eléctricas, turbinas, transporte de combustible, energía solar, etc.
7. TRÁFICO
• Regulación y control del tráfico, ferrocarriles, líneas de metro, etc.
 
• Semáforo: Las máquinas de estados nos
permiten identificar los diferentes estados de un sistema, así como los procesos o transiciones que ocurren para que dicho sistema cambie de un estado a otro como un semáforo:
• Control de trenes: un mecanismo muy simple que puede ser modelado por una máquina de estados es un torniquete, que se utiliza para controlar el acceso a los trenes subterráneos y un parque de diversiones.
APLICACIÓN DE LOS AUTOMATAS FINITOS EN SISTEMAS EMBEBIDOS PARAAPLICACIONES DE CONTROL (TRANSDUCCION)
HORNO MICROONDAS:
El horno microondas posee una puerta. Si la puerta está cerrada, entonces puede estar o no en funcionamiento (según se prenda o apague). Estando prendido no es posible abrir la puerta del horno sin antes apagarlo. También asumamos lo siguiente: en cualquier momento es posible establecer el modo de cocción.
TERMOSTATO:
Un termostato es el componente de un sistema de control simple que abre o cierra un circuito eléctrico en función de la temperatura, regula la potencia de calefacción(salida) en función a la temperatura ambiente (dato de entrada), pasando de un estado térmico a otro.
LAVADORA: Supongamos que disponemos de una lavadora, que externamente tiene tres botones: Encender, Detener, Lavar; de un indicador luminoso L, y de un interruptor ubicado en la puerta. Se consideran eventos (entradas) la activación de los botones de la consola del interruptor de la puerta. El indicador luminoso es una acción (salida)que debe ejecutarse. Se visualizan tres estados asociados a la lavadora: apagada, detenida y lavando.
APLICACIÓN DE LOS AUTOMATAS FINITOS EN COMUNICACIONES
1. PROTOCOLO DE COMUNICACIONES
Un protocolo de comunicaciones es el conjunto de reglas normalizadas para la representación, señalización, autenticación y detección de errores necesario para enviar información a través de un canal de comunicación. Un ejemplo de un protocolo de comunicaciones simple adaptado a la comunicación por voz es el caso de un locutor de radio hablando a sus radioyentes. Los protocolos de comunicación para la comunicación digital por redes de computadoras tienen características destinadas a asegurar un intercambio de datos fiable a través de un canal de comunicación imperfecto. Los protocolos de comunicación siguen ciertas reglas para que el sistema funcione apropiadamente.
2. TELEFONIA
La modelación con un autómata de las llamadas en esperase realiza a través del concepto de operación asociada a un estado, es decir una operación ejecutada continuamente en el estado, así el estado Tono Ocupado produce continuamente el tono ocupado por lo que se agrega en el estado la indicación: Hacer Tono Ocupado
(DEFINICIÓN DE UN CASO DE ESTUDIO)
• Interruptor de luz
• Control de máquinas de bebidas
• Analizadores/generadores de palabras
• Control de las tareas de un robot
• Búsqueda y sustitución de palabras
• Tratamiento de masas de textos
• Analizadores léxicos de compiladores y traductores
• etc.
Máquina de bebidas:
1. Las bebidas cuestan 25 céntimos.
2. Monedas que admite la máquina:
1. De cuarto, 25 céntimos (Q).
2. Dimea, 10 céntimos (D).
3. Nickel, 5 céntimos (N).
3. La máquina acepta cualquier combinación
de monedas hasta 25 céntimos.
4. La máquina requiere la cantidad exacta.