Teoria de automatas

Solo disponible en BuenasTareas
  • Páginas : 3 (696 palabras )
  • Descarga(s) : 0
  • Publicado : 11 de mayo de 2011
Leer documento completo
Vista previa del texto
TEORIA MATEMATICA
AUTOMATAS FINITOS Y GRAMATICAS REGULARES
La teoría de autómatas es una rama de las ciencias de la computación que estudia matemáticamente maquinas abstractas y problemas que estasson capases de resolver. La teoría de autómatas está estrechamente relacionada con la teoría de lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales queson capases de reconocer.
Un autómata es un modelo matemático para una maquina de estado finito (fsm). Una “fsm” es una máquina que, dada una entrada de símbolos, salta a través de una serie deestados de a cuerdo de una función de transición (que puede ser expresada como una tabla) esta función de transición dice al autómata a que estado cambiar dados unos determinados estados y símbolos. Laentrada es leída símbolo por símbolo hasta que es consumida completamente (piense en esta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata; la cabeza semueve a lo largo de la cinta leyendo un símbolo a la vez) una vez que la entrada se agota el autómata se detiene.
Dependiendo del estado en el que el autómata para, se dice que este a aceptado orechazado la entrada. Si este termina en el estado “acepta”, el autómata acepta la palabra, si lo hace en el estado “rechaza” el autómata rechaza la palabra, el conjunto de todas las palabras aceptadas porel autómata constituyen el lenguaje aceptado por el mismo.

Es aquel que solo puede estar
El termino determinista hace referencia al hecho de que para cada entrada existe un solo estado al que elautómata puede hacer la transición a su estado actual por el contrario un autómata finito no determinista puede estar en varios estados a la vez,.
El termino autómata finito hace referencia a lavariedad determinista, aunque normalmente utilizaremos el termino determinista o la abreviatura afd con el fin de recordar el tipo de autómata del que de esta ablando.

Definición de autómata finito...
tracking img