Teoria de la computación

Solo disponible en BuenasTareas
  • Páginas : 2 (414 palabras )
  • Descarga(s) : 0
  • Publicado : 23 de octubre de 2010
Leer documento completo
Vista previa del texto
ATOMATAS FIFNITOS:
AUTOMATAS 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 deentrada, empezando por el estado inicial.

Autómatas finitos deterministas

Las maquinas conocidas como autómatas finitos deterministas consisten en un dispositivo que puede estar en cualquiera deun número finito de estados, uno de los cuales es el estado inicial y por lo menos uno es el estado de aceptación. A este dispositivo está unido un flujo de entrada por medio del cual llegan ensecuencia los símbolos de un alfabeto determinado. La maquina tiene la capacidad para detectar los símbolos conforme llegan y, basándose en el estado actual y el símbolo recibido, ejecutar una transición(de estado) que consiste en un cambio a otro estado o la permanencia en el estado actual. La determinación de cual será precisamente la transición que ocurra al recibir un símbolo depende de unmecanismo de control de la maquina, programado para conocer cuál debe ser el nuevo estado dependiendo da la combinación del estado actual y el símbolo de entrada. La palabra “finito” se refiere a que lamaquina solo tiene un numero finito de estados. Un autómata finito regularmente es representado de la siguiente manera:

Cabeza de lectura

La cabeza se mueve en esta dirección.

Mecanismo decontrol
Indicador del estado

Los estados de posibles están representados en la circunferencia de este reloj y un apuntador indica el estado actual. El flujo de entrada a la maquina aparece como unacinta de papel dividida en celdas, cada una de las cuales es capaz de almacenar un símbolo. La maquina es capaz de leer los símbolos de esta cinta, de izquierda a derecha, por medio de una cabeza de...
tracking img