Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
Rocket clouds
Automatas Finitos por Mind Map: Automatas Finitos

1. Representacion de un ER en un AFND

1.1. ERs, AFDs y AFNDs son mecanismos equivalentes para denotar los lenguajes regulares. En estas tres secciones demostraremos esto mediante convertir ER →AFND → AFD → ER. Las dos primeras conversiones son muy relevantes en la práctica, pues permiten construir verificadores o buscadores eficientes a partir de ERs

1.1.1. Existen algoritmos que relacionan la especificación de tokens -expresiones regulares-, con el reconocimiento de éstos -autómatas finitos-. Es posible dada una expresión regular obtener el AFD que reconozca las cadenas del lenguaje denotado por la expresión regular. También es posible obtener el AFND que reconozca el lenguaje representado por dicha expresión regular.

2. Minimizacion de estados en un AF

2.1. 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 n o son equivalentes, se di ce que son estados distinguibles. Un estado final con un estado no- final nunca serán equivalentes.

2.1.1. 1. Eliminar los estados inaccesibles es 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 marcado

3. Aplicaciones

3.1. Industria

3.1.1. Automovil

3.1.1.1. Cadenas de montaje, soldadura, cabinas de pintura, transmisiones. Máquinas herramientas: Tornos, fresadoras, taladradoras, etc.

3.1.2. Plantas quimicas

3.1.2.1. Control de procesos (dosificación, mezcla, pesaje, etc). Baños electrolíticos, oleoductos, refinado, tratamiento de aguas residuales

3.2. Electronica

3.2.1. Creacion de circuitos

3.2.1.1. Reconocer que una cadena de símbolos se idéntica a otra y así dejar pasar los datos

3.3. Linguistica computacional

3.3.1. Compilador

3.3.1.1. 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

3.4. Red Neuronal Artificial

3.4.1. Redes de neuronas

3.4.1.1. Sistema de interconexión de neuronas en una red que colabora para producir un estímulo de salida

3.5. Aplicaciones de Control

3.5.1. Lavadora

3.5.1.1. Se visualizan tres estados asociados a la lavadora: apagada, detenida y lavando. La detección de cuáles son los estados, está basada en la visualización de situaciones distinguibles que se mantienen

3.5.2. Termostato

3.5.2.1. Sistema de control simple que abre o cierra un circuito eléctrico en función de la temperatura, regula la potencia de calefacción

3.5.3. Microondas

3.5.3.1. Si la puerta está cerrada, entonces puede estar o no en funcionamiento (según se prenda o apague)

3.6. Comunicacion

3.6.1. Protocolos de comunicacion

3.6.1.1. 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

3.6.2. Telefonia

3.6.2.1. Estado Tono Ocupado produce continuamente el tono ocupado por lo que se agrega en el estado la indicación : Hacer Tono Ocupado.

3.7. Inteligencia artificial

3.7.1. Maquinas Inteligentes

3.7.1.1. Creación de un agente inteligente que sea capaz de actuar y razonar como un humano, capaz de aceptar los símbolos y reconocer las cadenas que se están usando