Lenguajes Aceptados Por La Maquina De Turig
Páginas: 3 (524 palabras)
Publicado: 27 de febrero de 2013
Lenguajes aceptados por una maquina Turing
Aceptan lenguajes formales que pueden ser generados por una gramática de tipo 0: recursivamente innumerable. Las maquinas de Turing son losreconocedores de lenguaje más poderosos que existen.
Lenguajes regulares: las gramáticas (de tipo 3) formales definen un lenguaje describiendo como se pueden generar las cadenas del lenguaje… Las gramáticasregulares (aquellos reconocidos por un autómata finito). Son las gramáticas más restrictivas. El lado derecho de una producción debe contener un símbolo Terminal y como máximo un símbolo no Terminal.Máquinas de Turing Deterministas y no Deterministas
La entrada de una máquina de Turing viene determinada por el estado actual y el símbolo leído, un par [estado, símbolo], siendo el cambio deestado, la escritura de un nuevo símbolo y el movimiento las acciones a tomar en función de una entrada. En el caso de que para cada par estado y símbolo posible exista a lo sumo una posibilidad deejecución, se dirá que es una máquina de Turing determinista, mientras que en el caso de que exista al menos un par [estado, símbolo] con más de una posible combinación de actuaciones se dirá que se tratade una máquina de Turing no determinista.
La función de transición δ en el caso no determinista, queda definida como sigue:
¿Cómo sabe una máquina no determinista cuál de las varias actuacionestomar? Hay dos formas de verlo: una es decir que la máquina es "el mejor adivino posible", esto es, que siempre elige la transición que eventualmente la llevará a un estado final de aceptación. Laotra es imaginarse que la máquina se "clona", bifurcándose en varias copias, cada una de las cuales sigue una de las posibles transiciones. Mientras que una máquina determinista sigue un solo "caminocomputacional", una máquina no determinista tiene un "árbol computacional". Si cualquiera de las ramas del árbol finaliza en un estado de aceptación, se dice que la máquina acepta la entrada.
La...
Aceptan lenguajes formales que pueden ser generados por una gramática de tipo 0: recursivamente innumerable. Las maquinas de Turing son losreconocedores de lenguaje más poderosos que existen.
Lenguajes regulares: las gramáticas (de tipo 3) formales definen un lenguaje describiendo como se pueden generar las cadenas del lenguaje… Las gramáticasregulares (aquellos reconocidos por un autómata finito). Son las gramáticas más restrictivas. El lado derecho de una producción debe contener un símbolo Terminal y como máximo un símbolo no Terminal.Máquinas de Turing Deterministas y no Deterministas
La entrada de una máquina de Turing viene determinada por el estado actual y el símbolo leído, un par [estado, símbolo], siendo el cambio deestado, la escritura de un nuevo símbolo y el movimiento las acciones a tomar en función de una entrada. En el caso de que para cada par estado y símbolo posible exista a lo sumo una posibilidad deejecución, se dirá que es una máquina de Turing determinista, mientras que en el caso de que exista al menos un par [estado, símbolo] con más de una posible combinación de actuaciones se dirá que se tratade una máquina de Turing no determinista.
La función de transición δ en el caso no determinista, queda definida como sigue:
¿Cómo sabe una máquina no determinista cuál de las varias actuacionestomar? Hay dos formas de verlo: una es decir que la máquina es "el mejor adivino posible", esto es, que siempre elige la transición que eventualmente la llevará a un estado final de aceptación. Laotra es imaginarse que la máquina se "clona", bifurcándose en varias copias, cada una de las cuales sigue una de las posibles transiciones. Mientras que una máquina determinista sigue un solo "caminocomputacional", una máquina no determinista tiene un "árbol computacional". Si cualquiera de las ramas del árbol finaliza en un estado de aceptación, se dice que la máquina acepta la entrada.
La...
Leer documento completo
Regístrate para leer el documento completo.