Teoria de la computación
Páginas: 2 (414 palabras)
Publicado: 23 de octubre de 2010
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...
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...
Leer documento completo
Regístrate para leer el documento completo.