Inventarios

AUTÓMATAS Y MITOS
Autómata, del latín autómata y este del griego automatos (αὐτόματος), espontáneo o con movimiento propio. Según la RAE, máquina que imita la figura y los movimientos de un ser animado. Un equivalente tecnológico en la actualidad serían los robots autónomos. Si el robot es antropomorfo se conoce como androide.
El mundo de los autómatas es tan amplio como su definición. Entérminos bíblicos podríamos considerar al hombre como el primer autómata, creado del barro por Dios, aunque con la diferencia de poseer libre albedrío que le permite decidir por sí mismo. Esa distinción ha hecho que el ser humano haya querido imitar el acto de la creación desde el mismo inicio de su historia, construyendo mecanismos artificiales para todo tipo de fines desde científicos, deinvestigación, para agilizar sus tareas o por mero entretenimiento.
AUTÓMATAS FINITOS DETERMINISTAS
Un AFD o autómata finito determinista es aquel autómata finito cuyo estado de llegada está unívocamente determinado por el estado inicial y el carácter leído por el autómata.
Formalmente, un autómata finito determinista (AFD) es similar a un Autómata de estados finitos, representado con una 5-tupla(S,Σ,T,s,A) donde:
Σ es un alfabeto;
S un conjunto de estados;
T es la función de transición: ;
es el estado inicial;
es un conjunto de estados de aceptación o finales.
Es claro que, al contrario de la definición de Autómata finito, este es un caso particular donde no se permiten transiciones lamda (vacías), el dominio de la función T es S (con lo cual no se permiten transiciones desde unestado de un mismo símbolo a varios estados).
A partir de este autómata finito es posible hallar la expresión regular resolviendo un sistema de ecuaciones.
S1 = 1 S1 + 0 S2 + ε
S2 = 1 S2 + 0 S1
Siendo ε la palabra nula. Resolviendo el sistema y haciendo uso de las reducciones apropiadas se obtiene la siguiente expresión regular: 1*(01*01*)*.
Inversamente, dada la expresión regular es posiblegenerar un autómata que reconozca el lenguaje en cuestión utilizando el algoritmo de Thompson, desarrollado por Ken Thompson, uno de los principales creadores de UNIX, junto con Dennis Ritchie.
AUTÓMATAS FINITOS NO DETERMINISTAS
Un AFND o autómata finito no determinista es aquel que presenta cero, una o más transiciones por el mismo carácter del alfabeto .
Un autómata finito no deterministatambién puede o no tener más de un nodo inicial.
Los AFND también se representan formalmente como tuplas de 5 elementos (S,Σ,T,s,A). La única diferencia respecto al AFD es T.
AFD:
AFND: (partes de S)
Debido a que la función de transición lleva a un conjunto de estados, el automáta puede estar en varios estados a la vez (o en ninguno si se trata del conjunto vacío de estados).
Autómatasfinitos no deterministas con transiciones λ
Un AFND-λ o autómata finito no determinista con transiciones λ permite cambiar de estado sin procesar ningún símbolo de entrada. Cuando el autómata llega a un estado, se encuentra en ese estado y en los estados a los que apunte este mediante una transición λ.
Se representan formalmente con una tupla de 5 elementos, y se diferencian en los AFND en lafunción de transferencia:
AFND: (partes de S)
AFND-λ: (partes de S)
Cuando el símbolo de entrada es la palabra vacía (λ), existe una transición λ entre los estados.
AFD, AFND y AFND-λ
Para todo AFND-λ existe un AFND equivalente y para todo AFND existe un AFD equivalente.
Existen algoritmos para transformar un autómata en otro. Los AFD son los más sencillos de construir, por tanto, puedeser útil diseñar un autómamata complejo como AFND-λ o AFND para luego transformarlo en AFD para su implementación.
EXPRESIONES REGULARES
Las expresiones regulares constituyen un mecanismo bastante potente para realizar manipulaciones de cadenas de texto. El proceso para el que se usan estas expresiones, presente en el mundo el UNIX y el lenguaje Perl, es el de buscar y/o substituir una...