Maquina de estados finitos

Una máquina de estados finitos en un modelo abstracto para la manipulación de símbolos, nos permiten saber si una cadena pertenece a un lenguaje o nos pueden generar otro conjunto de símbolos como resultado. Llamaremos una Máquina de Estados Finitos como Autómata Finito, el hecho es que un Autómata y una Máquina de Estados Finitos son lo mismo, podemos utilizar ambos términos de forma indistinta. Los Autómatas se caracterizan por tener un Estado inicial, reciben una cadena de símbolos, cambian de estado por cada elemento le ‘ido o pueden permanecer en el mismo estado. También tienen un conjunto de Estados Finales o Aceptables que nos indican si una cadena pertenece al lenguaje al final de una lectura.

Los Autómatas se clasifican en 2 tipos:

·         Autómata Finito Determinista.

·         Autómata Finito no Determinista.

Siempre llamamos un Autómata como Autómata Finito, esto nos puede llevar a pensar que existe algún tipo de Autómata Infinito, lo cual no tiene mucho sentido pensar en un tipo de Máquina que tiene un conjunto infinito de estados, pero aún se discute su utilidad para propósitos prácticos. Un “Autómata Infinito” tiene cintas infinitas o registros de almacenamiento de capacidad ilimitada, esto le da el carácter de infinito

Autómatas Finitos Deterministas.

Un Autómata recibe secuencialmente una cadena de símbolos y cambia de estado por cada símbolo leído o también puede permanecer en el mismo estado. Al final de la lectura el estado del Autómata nos indica si la cadena es aceptada o mejor dicho pertenece al Lenguaje que describe nuestra máquina. Si al final de leer todos los símbolos de entrada la máquina está en alguno de los estados Finales entonces esa cadena es aceptada, si el estado no es final entonces la cadena no pertenece al lenguaje. Las partes que componen una Autómata son 5 y se pueden definir:

A = {Q, q0, F, Σ, δ}

donde:

Q: Conjunto finito de estados.

q0: Estado inicial donde q0 ∈ Q. Debe haber uno y sólo un estado inicial.

F: Conjunto de estados finales F ⊆ Q. El estado q0 también puede ser final.

Σ: Alfabeto finito de entrada.

δ: Función de Transición Q × Σ → Q

Supongamos que el Autómata se encuentra en el estado qi donde qi ∈ Q, también tenemos el símbolo a donde a ∈ Σ. Una entrada a causa que el Autómata cambie del estado qi al estado qk. La función δ, llamada función de transición, describe este cambio de la forma δ(qi , a) → qk de esta forma obtenemos un nuevo estado. Se entiende por transición como el proceso que hace un Autómata al cambiar de estado.

En un diagrama de transición existe un nodo por cada estado qi de Q. Los estados finales están encerrados en un círculo doble. El estado inicial q0 es apuntado por una flecha que no proviene de ningún otro estado. Para cada estado qi y un símbolo a, hay exactamente una y sólo una flecha que inicia en qi y termina en δ(qi , a), es decir en qk, la flecha es etiquetada como a. Si qk pertenece a F decimos que la entrada es aceptada. Debe haber exactamente una flecha saliendo de cada estado por cada símbolo a0, a1, a2... an, por tanto, todos los estados tienen el mismo número de flechas saliendo de cada uno de ellos. Con esto garantizamos que nuestro Autómata pueda ser llamado Determinista. No importa el estado ni el símbolo leído, siempre hay una transición definida. Para describir por completo una función de transición δ ocupamos una Tabla de Transición. Las columnas se etiquetan con los símbolos de entrada, la filas son etiquetadas con los estados y en las intersecciones se colocan los nuevos estados δ(qi , a), suponiendo que qi ∈ Q es la columna y a ∈ Σ la fila que lo interseca. La tabla de transición de la figura 1 es:

El estado inicial tiene una flecha que apunta a ´el, los estados finales tienen una flecha que sale de ellos y los estados que no son finales y no son el inicial no tienen flecha. En caso de que nuestro estado inicial también sea un estado final, se apuntará con una flecha doble ↔.


BIBLIOGRAFÍA 

(s. f.). Servidor del Departamento de Computacióon. http://delta.cs.cinvestav.mx/~mcintosh/cellularautomata/Summer_Research_files/maquinasef.pdf






Comentarios

Publicar un comentario

Entradas populares de este blog

ARREGLO LOGICO GENERICO (GAL)

Imagen
   JAVIER MICHEL FLORES COYOTL   GAL  GAL (Generic Array Logic), en español Arreglo Lógico Genérico, son un tipo de circuito integrado, de marca registrada por Lattice Semiconductor, que ha sido diseñados con el propósito de sustituir a la mayoría de las PAL, manteniendo la compatibilidad de sus terminales. Utiliza una matriz de memoria EEPROM en lugar por lo que se puede programar varias veces. Un GAL en su forma básica es un PLD con una matriz AND reprogramable, una matriz OR fija y una lógica de salida programable mediante una macrocelda. Esta estructura permite implementar cualquier función lógica como suma de productos con un número de términos definido. En los PLDs no reprogramables la síntesis de las ecuaciones lógicas se realiza mediante quema de fusibles en cada punto de intersección de los pines de entrada con las compuertas. En el caso de un GAL es básicamente la misma idea pero en vez de estar formada por una red de conductores ordenados en filas y col...
Leer más

Función "rising_edge" para VHDL

Esta instrucción detecta el flanco ascendente de una  señal  std_ulogic   o  std_logic .  Devolverá verdadero cuando la señal cambie de un valor bajo (  '0' o  'L' ) a un valor alto (  '1' o  'H' ). Ejemplo En este ejemplo, el simulador ejecuta el cuerpo del  if  exactamente una vez por ciclo de reloj, en el flanco ascendente de la señal de reloj. signal clock : std_logic; ... sync_stuff: process (clock) begin if rising_edge(clock) then ... end if; end process; En pocas palabras, cuando detecta un 1 nos devolvera un 1 y si no detecta nada no nos devolvera ningun valor. Referencia The rising_edge function . (s. f.). Computing Science - Simon Fraser University.  https://www2.cs.sfu.ca/~ggbaker/reference/std_logic/1164/rising_edge.html
Leer más

Señal del reloj en VHDL

En los sistemas digitales el reloj es el elemento que marca el sincronismo entre todos los elementos del circuito. Cada vez que hay un cambio, normalmente de 0 a 1, del reloj, los elementos de memoria, llamados biestables o flip-flops se cargan con los nuevos datos calculados durante el periodo transcurrido entre el cambio anterior y el actual. El tiempo que tarde la señal en llegar de su origen a su destino entre dos pulsaciones de este corazón eléctrico, lo denominamos el  camino crítico del circuito , y es la velocidad máxima a la que puede latir el reloj, ya que si fuera más rápido las señales no serían estables a las entradas de los flips-flops y el circuito comenzaría a dar resultados erróneos. library IEEE; use IEEE.STD_LOGIC_1164.ALL; entity clk_div is generic (divider : integer range 0 to 1023); port ( clk_i : in std_logic; clk_o : out std_logic Bibliografía: vhdl_es. (2019, 5 de febrero).  Dividir el reloj en una FPGA - VHDL.es . VHDL.es....
Leer más