• Author / Uploaded
• juanmro

• Categories
• Matemáticas
• Ciencia
• Informática y tecnología de la información
• Ciencia y Tecnología
• Tecnología (general)

Citation preview

AUTÓMATAS FINITOS MOORE Y MEALY UNIVERSIDAD UNIMINUTO INSTITUTO DE EDUCACION A DISTANCIA CONTROLADORES PROGRAMABLES

Por: Ing. John Jaiver Muñoz

Introducción a los autómatas Antes de que existieran las computadoras, en la década de los años treinta, A. Turing estudió una máquina abstracta que tenía todas las capacidades de las computadoras de hoy día, al menos en lo que respecta a lo que podían calcular. El objetivo de Turing era describir de forma precisa los límites entre lo que una máquina de cálculo podía y no podía hacer; estas conclusiones no sólo se aplican a las máquinas abstractas de Turing, sino a todas las máquinas reales actuales.

¿Por qué estudiar la teoría de autómatas? Son varias las razones por las que el estudio de los autómatas y de la complejidad de cálculo constituyen una parte importante del núcleo de la Ciencias de la Computación. la teoría de los autómatas que estudia los métodos de construcción de los sistemas para el procesamiento de la información.

Teoría de autómatas La teoría de autómatas se ocupa de clasificar y estudiar de modo sistemático diferentes tipos de maquinas abstractas que llevan a cabo un procesamiento secuencial de la información.

Introducción a los autómatas finitos Los autómatas finitos constituyen un modelo útil para muchos tipos de hardware y software. 1. Software para diseñar y probar el comportamiento de circuitos digitales. 2. El “analizador léxico” de un compilador típico, es decir, el componente del compilador que separa el texto de entrada en unidades lógicas, tal como identificadores, palabras clave y signos de puntuación. 3. Software para explorar cuerpos de texto largos, como colecciones de páginas web, o para determinar el número de apariciones de palabras, frases u otros patrones. 4. Software para verificar sistemas de todo tipo que tengan un número finito de estados diferentes, tales como protocolos de comunicaciones o protocolos para el intercambio seguro de información.

Autómata finito El concepto de autómata es mucho mas genérico, ya que podemos considerarlo como un dispositivo que procesa cadenas de símbolos que recibe como entrada, cambiando de estado y produciendo una salida que, en algunos casos, puede estar formada por otra cadena de símbolos.

Ejemplo autómata finito Autómata finito que podría formar parte de un analizador léxico. El trabajo de este autómata consiste en reconocer la palabra clave then, por lo que necesita cinco estados, representando cada uno de ellos la posición dentro de dicha palabra que se ha alcanzado hasta el momento. Estas posiciones se corresponden con los prefijos de la palabra, desde la cadena de caracteres vacía (es decir, cuando no contiene ningún carácter) hasta la palabra completa. Podemos imaginar que el analizador léxico examina un carácter del programa que se está compilando en un determinado instante, y que el siguiente carácter que se va a examinar es la entrada al autómata.

Representaciones estructurales Existen dos importantes notaciones que no son las utilizadas normalmente con los autómatas:  Las gramáticas son modelos útiles en el diseño de software que sirve para procesar datos con una estructura recursiva. Por ejemplo, una regla gramatical como E⇒E+E establece que una expresión puede formarse tomando cualesquiera dos expresiones y conectándolas mediante un signo más. 

Las expresiones regular es también especifican la estructura de los datos, especialmente de las cadenas de texto.

Máquinas de estados finitos 







Permite reconocer secuencias de eventos “aceptables”.

Los nombres de los eventos van a estar formados por un carácter, y les llamaremos transiciones en vez de “eventos”. Las secuencias de eventos van a representarse por concatenaciones de caracteres, esto es, por palabras. Al ser visualizadas como dispositivos con los siguientes componentes:  Una cinta de entrada;  Una cabeza de lectura (y eventualmente escritura);  Un control.

Máquinas de estados finitos

La cabeza lectora se coloca en los segmentos de cinta que contienen los caracteres que componen la palabra de entrada, y al colocarse sobre un carácter lo “lee” y manda esta información al control; también puede recorrerse un lugar a la derecha (o a la izquierda también, según el tipo de máquina). El control (indicado por una caratula de reloj en la figura) le indica a la cabeza lectora cuándo debe recorrerse a la derecha. Se supone que hay manera de saber cuándo se acaba la entrada (por ejemplo, al llegar al blanco). La “aguja” del control puede estar cambiando de posición, y hay algunas posiciones llamadas finales (como la indicada por un punto, q3) que son consideradas especiales, porque permiten determinar si una palabra es aceptada o rechazada

Funcionamiento de los autómatas finitos El funcionamiento de los autómatas finitos consiste en ir pasando de un estado a otro, a medida que va recibiendo los caracteres de la palabra de entrada. Este proceso puede ser seguido fácilmente en los diagramas de estados. Simplemente hay que pasar de estado a estado siguiendo las flechas de las transiciones, para cada carácter de la palabra de entrada, empezando por el estado inicial.

Definición formal de autómatas finitos El formato matemático para representar las mismas informaciones que contiene un diagrama de estados. Como se utiliza terminología matemática en vez de dibujos, decimos que se trata de una notación formal. Definición.- Una máquina de estados finitos M es un quíntuplo (K, Σ, δ, s, F), donde: 

K es un conjunto de identificadores (símbolos) de estados;



Σ es el alfabeto de entrada;



s ∈ K es el estado inicial;



F ⊆ K es un conjunto de estados finales;



δ : K × Σ → K es la función de transición, que a partir de un estado y un símbolo del alfabeto obtiene un nuevo estado.

Definición formal de autómatas finitos La función de transición indica a qué estado se va a pasar sabiendo cuál es el estado actual y el símbolo que se está leyendo. Es importante notar que δ es una función y no simplemente una relación; esto implica que para un estado y un símbolo del alfabeto dados, habrá un y solo un estado siguiente. Esta característica, que permite saber siempre cual será el siguiente estado, se llama determinismo. La definición dada arriba corresponde a los autómatas finitos deterministas, abreviado “AFD”.

Autómatas Finitos Deterministas. Introducción 





Un autómata finito es un conjunto de estados y un control que se mueve de un estado a otro en respuesta a entradas externas. Los autómatas finitos se pueden clasificar en función del tipo de control como: 

Deterministas, el autómata únicamente puede estar en un estado en un momento determinado.



No Deterministas, el autómata puede estar en varios estados simultáneamente.

Ambos definen los mismos lenguajes (regulares), sin embargo los No deterministas permiten describir más eficientemente determinados problemas.

¿Cómo procesa entradas un AFD? 





La entrada a un AF es un conjunto de símbolos tomados del alfabeto de entrada ∑, no hay límite en tamaño de la cadena. Existe un “puntero” que en cada momento apunta a una posición de la cadena de entrada. El autómata está siempre en un estado de Q, inicialmente se encuentra en el estado q0.

¿Cómo procesa entradas un AFD? En cada paso el autómata lee un símbolo de la entrada y según el estado en el que se encuentre, cambia de estado y pasa a leer otro símbolo.





Así sucesivamente hasta que se terminen de leer todos los símbolos de la cadena de entrada.

Si en ese momento el AF está en un estado qi de F, se dice que acepta la cadena, en caso contrario la rechaza.

Tablas de transición. 





Es una representación clásica de una función con dos argumentos.

En las filas se colocarán los estados y en las columnas los símbolos del alfabeto de entrada. Cada intersección fila (estado q) - columna (carácter a) corresponde al estado f(q,a).



El estado inicial se representa con 



Los estados finales con un *

Diagramas de transición. 



 

Es un grafo en el que los vértices representan los distintos estados y los arcos las transiciones entre los estados. Cada arco va etiquetado con el símbolo que corresponde a dicha transición. El estado inicial se representa con  Los estados finales con un con doble círculo.

Representación AF 

Determinismo porque:   



No existen transiciones λ Una sola arista etiquetada con a para cada símbolo; Para cada entrada en la tabla un solo estado

La indeterminación en el caso que falten transiciones para algunas entradas se resuelve incluyendo un nuevo estado, llamado de absorción o muerto, al cual llegan todas las transiciones no definidas

Ejemplo 

El autómata finito determinista de la figura puede ser expresado formalmente como: M = (K, Σ, δ, q0, F ), donde:

La función de transición δ

Palabras aceptadas AFD Decimos que un AFD reconoce o acepta una palabra si se cumplen las siguientes condiciones: 



1. Se consumen todos los caracteres de dicha palabra de entrada, siguiendo las transiciones y pasando en consecuencia de un estado a otro; 2. al terminarse la palabra, el estado al que llega es uno de los estados finales del autómata (los que tienen doble círculo en los diagramas, o que son parte del conjunto F en la representación formal).

El concepto de lenguaje aceptado es una simple extensión de aquel de palabra aceptada: Definición.- El lenguaje aceptado por una máquina M es el conjunto de palabras aceptadas por dicha máquina.

Autómatas finitos con salida

Autómatas finitos con salida Por ejemplo, en el contexto de una máquina controlada por un autómata, puede haber distintas señales de salida que correspondan a los comandos enviados a la maquina para dirigir su acción.

Máquinas de Moore En las máquinas de Moore la salida depende del estado en que se encuentra el autómata. Dicha salida es producida una vez, y cuando se llega a otro estado (o al mismo) por efecto de una transición, se produce el símbolo de salida asociado al estado al que se llega. Se define por la quíntupla M = {∑E, ∑s, Q, f, g} 

∑E = Alfabeto de entrada



∑s= Alfabeto de salida



Q: Conjunto finito no vacio de estados



f: función de transacción. 



f: Q x ∑E  Q

g: Función de salida 

f: Q  ∑s

Máquinas de Mearly En las maquinas de Mealy la salida producida depende de la transición que se ejecuta, y no solamente del estado. Por esto, en la notación grafica las etiquetas de las flechas son de la forma σ/w, donde σ es el carácter que se consume de entrada, y w es la palabra que se produce en la salida. 

Se define por la quíntupla M = {∑E, ∑s, Q, f, g}  ∑E = Alfabeto de entrada  ∑s= Alfabeto de salida  Q: Conjunto finito no vacio de estados  f: función de transacción.  F: Q x ∑E  Q  g: Función de salida  g: Q x ∑E  ∑s

Comparación MS 



MS de Mealy  g: Q x ∑E  ∑s  g(q, a) = b Infinita, la salida solo depende de la entrada.

MS de Moore  g: Q  ∑s  g(q) = b 



Finita, la salida depende solo del estado. MS de Moore; caso particular de MS de Mealy.

 Velocidad de transmisión de la información dentro de la MS

REPRESENTACIÓN DE LAS MS 







Las máquinas secuenciales pueden representarse por:

1. Dos tablas:  Tabla de transiciones, tabla de f  Tabla de doble entrada  Tabla de salidas, tabla de g  MS de Mealy: Tabla de doble entrada  MS de Moore: Tabla de simple entrada 2. Una sola tabla de transiciones y de salidas, tabla de f y g 

MS de Mealy: entrada de la tabla f(q,a)/s



MS de Moore: entrada de la tabla f(q,a)

3. Diagramas de Transición

Dos tablas: tablas de transición y de salida Las funciones de transición (f) son las encargadas de dirigir a la máquina secuencial de un estado a otro. La estructura es la misma para las máquinas de Mealy y Moore: 

Filas: estados posibles de la máquina, qi ϵ Q



Columnas: símbolos del alfabeto de entrada, am ϵ ∑E

Dos tablas: tablas de transición y de salida Las funciones de salida (g) se encargan de seleccionar la salida correspondiente para cada máquina secuencial: 



En función del estado actual y la entrada que se reciba, en el caso de la máquina de Mealy. 

Filas: estados posibles de la máquina, qi ϵ Q



Columnas: símbolos del alfabeto de entrada, am ϵ ∑E

En función del estado en que se encuentren, en el caso de la máquina de Moore. 

Filas: estados posibles de la máquina, am ϵ ∑E

Dos tablas: tablas de transición y de salida

TABLAS DE TRANSICIÓN Y DE SALIDA. Ejemplo 



Ejemplo: Obtener la tabla de transición y de salida para las funciones de transición y de salida, respectivamente, de la siguiente máquina de Mealy:

Ejemplo: Obtener la tabla de transición y de salida para las funciones de transición y de salida, respectivamente, de la siguiente máquina de Moore:

Una sola tabla: TRANSICIÓN Y DE SALIDA 

Filas: estados posibles de la máquina, qi ϵ Q



Columnas: símbolos del alfabeto de entrada, am ϵ ∑E

Diagrama de transición Una MS puede ser representada a través de un grafo dirigido. Máquina secuencial de Mealy 



Las máquinas de Mealy tienen tantos estados como elementos tiene el conjunto Q y son etiquetados con el nombre de dicho elemento. Los cambios de estados se reflejan mediante una rama, de forma que si f(q,1)=r, dibujaremos una rama desde q hasta r. Si además g(q,1)=0, etiquetaremos dicha rama como 1/0. Ejemplo: Diseñar el diagrama de transición asociado a la máquina de Mealy definida en el ejemplo del apartado anterior.

Diagrama de transición Máquina secuencial de Moore 



Las máquinas de Moore tienen tantos estados como elementos tiene el conjunto Q y son etiquetados con el nombre de dicho elemento. Los cambios de estados se reflejan mediante unarama, de forma que si f(q,1)=r,dibujaremos una rama desde q hasta r etiquetada con 1. Si además g(q,1)=0, etiquetaremos el estado como r/0.

Ejemplo: Diseñar el diagrama de transición asociado a la máquina de Moore definida en el ejemplo del apartado anterior.

Ejemplo. MÁQUINA DE MEALY

Ejemplo. MÁQUINA DE MOORE

Preguntas….

Muchas Gracias……