Aplicaciones de Automatas y Expresiones Regulares
Transcript of Aplicaciones de Automatas y Expresiones Regulares
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 1/15
Gregory Del RiscoDaniel Perez
Kevin Tellez
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 2/15
Los autómatas y las expresiones regularestienen diversas aplicaciones en el ámbito delas ciencias de la computación como en laseguridad de redes, la generación de código,entre otros.
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 3/15
Dada una expresión regular al pasar alautómata resultante, dicho autómata debeser capaz de reconocer si determinadacadena pertenece o no al lenguaje que definela expresión regular inicial.
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 4/15
Este proceso presenta el problema de nopoder determinar la posición exacta de sub-
expresión de la expresión regular cuando lacadena si coincide con el lenguaje, existenalgoritmos para resolver ese problema peroestos son poseen complejidades muy
elevadas.
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 5/15
Los autómatas finitos no deterministicos contransiciones etiquetadas son iguales a los
autómatas finitos no deterministicos pero conetiquetas en sus transiciones las cuales tienela forma donde x es un numero entero.
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 6/15
Se propone un programa o un circuito de alta
velocidad para comprobar la coincidencia deun patrón determinado en un texto dado, locual puede ser aplicado en la detección deintrusos en redes, debido a la arquitectura
sistólica del circuito la cual consta deunidades de procesamiento simples.
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 7/15
Este proyecto trata del reconocimiento deuna determinada subclase de una
determinada expresión regular, el patrón espuesto en el circuito antes de iniciar lacomprobación de coincidencia y el texto paraser recuperado se introduce en el circuito
carácter por carácter.
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 8/15
Esta nueva propuesta de sistema de detecciónde intrusos en redes la cual consta del motorde comprobación de coincidencia de
patrones, este motor esta constituido por unarray sistólico de unidades de procesamientosimple el cual es denominado celda decomparación.
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 9/15
En algunos de los reconocedores deexpresiones regulares se presentan
problemas debido a que se producen latcheso “pestillos” esto es una consecuencia que seda debido a la interacción entre celular oceldas en el compilador lo cual altera el
correcto funcionamiento del reconocedor.
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 10/15
Por ello la idea es realizar una transformaciónque elimine la expresión que ocasiona laaparición del latch o pestillo , a diferencia delas soluciones anterior que agrandaban losreconocedores y alteraban la velocidad en laque trabajaba el reconocedor.
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 11/15
Al referir los autómatas finitos a lacompresión de videos nos da la posibilidadde reconocer si un archivo de cualquierextensión de video es modificado.
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 12/15
En este contexto de video-compresióndebemos tener en cuenta las técnicas decodificación que son:
• Intraframe
• Interframe
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 13/15
Teorema1: dado un autómata finitodeterminístico M sobre ∑, entonces existe una
expresión regular e, que cumple L (M)=L (e) yviceversa.
Transformar de un autómata
finito determinístico a una expresión regular.
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 14/15
Teorema2: se asume que K es unnodo en un autómata finitodeterminístico M y tiene un ciclosimilar al que se presenta en lafigura5. Dejando k como unaexpresión regular
correspondiente al sub-AFDdonde K es el estado de inicio yel estado de finalización almismo tiempo, entonces laetiqueta “t” sobre la arista (T,K)puede ser eliminada cuando seconstruye un ciclo con la etiqueta
“ke” sobre el nodo K, donde, “t”pertenece al alfabeto ∑. Nóteseque el nodo K y el nodo T seconservan.
5/17/2018 Aplicaciones de Automatas y Expresiones Regulares - slidepdf.com
http://slidepdf.com/reader/full/aplicaciones-de-automatas-y-expresiones-regulares 15/15
Prueba: primero se construye elautómata FA K como se muestra enla figura.
Después tenemos que en la figura7
que nos muestra un nuevo autómataque eliminó la arista “t” y construyóun ciclo con la arista ke sobre elnodo K. la diferencia es que no sepuede devolver por α a otro lado por
K.