Automatas Finitos Introduccion

Automatas Finitos Introduccion

MEZA DE LOS PALOS ANA KAREN

Un Automata finito es similar a una maquina de estado finito sin embargo lo que caracteriza a una de la otra es que los automatas finitos solo tienen dos estados, un estado interno y uno de rechazo. esta formado por una quintupla <A,S,T,q0, F>. A= Simbolos de entrada S= Estados internos T= un Subconjunto de S (Estado de Aceptacion) q0= Estado inicial F= Funcion de proximo estado F= S x A -→ S.

 :::::: INSTITUTO TECNOLOGICO DE TIJUANA……..

INTRODUCCION DE LOS AUTOMATAS FINITOS

Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.

FORMAS DE REPRESENTACION DE UN AUTOMATA FINITO

Además de notar un AF a través de su definición formal es posible representarlo a través de otras notaciones que resultan más cómodas.

	Las Expresiones regulares. Se demuestra que dado un autómata de estados finitos, existe una expresión regular que lo representa. 
        Ø υ 1* υ (1* ο 0 ο 1* ο 0)*

Descripción informal de su funcionamiento

En el comienzo del proceso de reconocimiento de una cadena, el AF se encuentra en el estado inicial y a medida que procesa cada símbolo de la cadena va cambiando de estado de acuerdo a lo determinado por la función de transición. Cuando se ha procesado el último de los símbolos de la cadena de entrada, el autómata se detiene. Si el estado en el que se detuvo es un estado de aceptación o final, entonces la cadena pertenece al lenguaje reconocido por el autómata, caso contrario, la cadena no pertenece a dicho lenguaje.

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.

Al contrario de la definición de autómata finito, este es un caso particular donde no se permiten transiciones lambda (vacías), el dominio de la función T es S (con lo cual no se permiten transiciones desde un estado 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 posible generar 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. Un tipo de autómatas finitos deterministas interesantes son los tries.

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 determinista tambié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ómatas finitos 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 λ.

Un automata es un 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, puede ser útil diseñar un autómata complejo como AFND-λ o AFND para luego transformarlo en AFD para su implementación.


 Los Automatas finitios constituyen un modelo util para muchos tipos importantes de hardware y software. Estos son algunos ejemplos:

1.- Software para el diseño y la verificacion del comportamiento de circuitos digitales.

2.- El analizador lexico de un compilador tipico, esto es la componente del compilador que descompone el texto inicial en unidades logicas tales como identificadores, palabras reservadas y signos de puntuacion.

3.-Software para explorer grandes corpus de texto, como conjuntos de oaguinas web, o para descubrir las apariciones de ciertas palabras, frases u otros patrones.

4.- Software para comprobra la correction de cualquier tipo de sistemas que tengan un numero finito de estados diferentes.

La ventaja de tener solo un numero finito de estados es que el sistema se puede implementar con un volumen fijo de recursos. Por ejemplo podria hacerce una implementacion de hardware con un circuito, o mediante un un programa sencilla que decida en function de un Conjunto limitados de datos.

En los automata finites, los estado se representan mediante circulos; en este ejemplo es on y off. Los arcos entre los estados se han etiquetado mediante “entradas”, que representan las influencias externas que afectan el sistema. En este caso los dios arcos se han etiquetado con la entrada pulsar, que representa la accion realizada por un usuario al pulsar el boton. Los arcos nos indicant que, sea cual sea el estado en que se encuentre el sistema, cuando se recibe la entrada pulsar el sistema cambia al otro estado. Uno de los estados del automata se denomina “estado inicial” es qem el que se situa inicialmente el sistema. Es necesario indicar que uno o mas estados son “estados finales” o “estados de aceptacion”. Es conveniente que el sistema llegue a uno de estos estados despues de una secuencia de entradas sucesivas.


AUTOMATAS DE PILA

Un autómata con pila o autómata de pila o autómata a pila o autómata apilador es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce. El lenguaje que reconoce un autómata a pila pertenece al grupo de los lenguajes de contexto libre en la clasificación de la Jerarquía de Chomsky.

EJEMPLOS

Formalmente, un autómata con pila puede ser descrito como una séptupla M = (S,Σ,Γ,δ,s,Z,F) donde:

* Σ y Γ son alfabetos de entrada, de la cadena y de la pila respectivamente;
* S un conjunto de estados;
* \delta: S \times (\Sigma \cup \{\epsilon \} ) \times \Gamma \rightarrow \mathcal{P} ( S \times \Gamma^*) * s \in S es el estado inicial; * Z\ \in \Gamma es el símbolo inicial de la pila; * F \subseteq S es un conjunto de estados de aceptación o finales.

La interpretación de \delta (s, a, Z) = \{ (s_1, \gamma_1), (s_2, \gamma_2), \ldots, (s_n, \gamma_n) \}, con s, p_i \in Q, a \in (\Sigma \cup \{ \epsilon \} ), \gamma_i \in \Gamma es la siguiente:

Cuando el estado del autómata es s, el símbolo que la cabeza lectora está inspeccionando en ese momento es a, y en la cima de la pila nos encontramos el símbolo Z, se realizan las siguientes acciones:

    * Si a \in \Sigma, es decir no es la palabra vacía, se avanza una posición la cabeza lectora para inspeccionar el siguiente símbolo.
    * Se elimina el símbolo Z de la pila del autómata.
    * Se selecciona un par (pi,γi) de entre los existentes en la definición de δ(s,A,Z), la función de transición del autómata.
    * Se apila la cadena \gamma_i = A_1 A_2 \ldots A_k en la pila del autómata, quedando el símbolo A1 en la cima de la pila.
    * Se cambia el control del autómata al estado pi.

Da clic para ver el video sobre Automas de Pila:

http://www.youtube.com/watch?v=pV1m831fg3M

302 Lic. en Informatica

Rocio Higuera Eseverre. Erika Valadez Guerra. Ackerman Arredondo Roberto Jr.


AUTOMATA DETERMINISTA

Nótese que, a diferencia de un autómata finito o una máquina de Turing, la definición básica de un autómata con pila es de naturaleza no determinista, pues la clase de los autómatas con pila deterministas, a diferencia de lo que ocurría con aquellos modelos, tiene una potencia descriptiva estrictamente menor. Para calificar a un autómata con pila como determinista deben darse dos circunstancias; en primer lugar, por supuesto, que en la definición de cada componente de la función de transición existan un único elemento lo que da la naturaleza determinista. Pero eso no es suficiente, pues además puede darse la circunstancia de que el autómata esté en el estado s y en la pila aparezca el símbolo sZ, entonces, si existe una definición de transición posible para algún símbolo cualquiera a del alfabeto de entrada, pero, además existe otra alternativa para la palabra vacía ε, también esto es una forma de no determinismo, pues podemos optar entre leer un símbolo o no hacerlo. Por eso, en autómata determinista no debe existir transición posible con lectura de símbolo si puede hacerse sin ella, ni al contrario.

Para cada q \in Q, Z \in \Gamma, se dé que: \mid \delta(q,\epsilon,Z)\mid + \mid \delta(q,a,Z)\mid \le 1 , para cada a \in \Sigma

302 Lic. en Informatica

Rocio Higuera Eseverre. Erika Valadez Guerra. Ackerman Arredondo Roberto Jr.


Mis sitios nuevos:
Emprendedores
Politica de Privacidad