Identificacion de maquinas de esta algoritmico

Solo disponible en BuenasTareas
  • Páginas : 7 (1708 palabras )
  • Descarga(s) : 0
  • Publicado : 28 de noviembre de 2010
Leer documento completo
Vista previa del texto
La Máquina de estados algorítmica (ASM)

Es un método para el diseño de Máquina de estados finitos. Un autómata finito (AF) o máquina de estado finito es un modelo matemático. Modelo matemático es uno de los tipos de modelos científicos, que emplea algún tipo de formulismo matemático para expresar relaciones, proposiciones sustantivas de hechos, variables, parámetros, entidades y relacionesentre variables y/o entidades u operaciones, para estudiar comportamientos de sistemas complejos ante situaciones difíciles de observar en la realidad. El término modelización matemática es utilizada también en diseño gráfico cuando se habla de modelos geométricos de los objetos en dos (2D) o tres dimensiones (3D). Que realiza cómputos en forma automática sobre una entrada para producir una salida.Máquina de Turing (MT) es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.
Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco(normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados. Sufuncionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres(la cinta, la cual es finita por la izquierda) pertenecientes al alfabeto de entrada. Luego va leyendo una celda de la cinta, borrando el símbolo, escribir el nuevo símbolo perteneciente al alfabeto de salida y finalmente avanza a la izquierda o a la derecha(solo una celda a la vez), repitiendo estosegún se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.
Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida.
Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transicionesentre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.
La finalidad de los autómatas finitos esla de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky. En lingüística la jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956.

La Jerarquía de Chomsky consta de cuatro niveles:
• Gramáticas de tipo0 (sin restricciones), que incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes capaces de ser reconocidos por una máquina de Turing. Los lenguajes son conocidos como lenguajes recursivamente enumerables. Nótese que esta categoría es diferente de la de los lenguajes recursivos, cuya decisión puede ser realizada por una máquina de Turing que se detenga.
•Gramáticas de tipo 1 (gramáticas sensibles al contexto) generan los lenguajes sensibles al contexto. Estas gramáticas tienen reglas de la forma [pic]con A un no terminal y α, β y γ cadenas de terminales y no terminales. Las cadenas α y β pueden ser vacías, pero γ no puede serlo. La regla [pic]está permitida si S no aparece en la parte derecha de ninguna regla. Los lenguajes descritos por estasgramáticas son exactamente todos aquellos lenguajes reconocidos por una máquina de Turing determinista cuya cinta de memoria está acotada por un cierto número entero de veces sobre la longitud de entrada, también conocidas como autómatas linealmente acotados.
• Gramáticas de tipo 2 (gramáticas libres del contexto) generan los lenguajes independientes del contexto. Las reglas son de la forma...
tracking img