icuando se habla de autómata, nos referimos a máquinas (abstractas o no) que sean capaces de...
DESCRIPTION
Cuando se habla de autómata, nos referimos a máquinas (abstractas o no) que sean capaces de computar. Las máquinas de Turing son un ejemplo de un autómata tan complejo que es capaz de resolver todos los problemas que una computadora actual puede resolver con precisión. Sin embargo, existen autómatas más simples que éstos, como los autómatas finitos o los autómatas de pila. Los autómatas finitos tienen relación con los lenguajes regulares y las expresiones regulares, mientras que los autómatas de pila tienen relación con los lenguajes y las gramáticas de contexto libre. Las expresiones regulares se usan en la actualidad para la búsqueda de patrones en textos, mientras que las gramáticas de contexto libre juegan un papel escencial en la implementación de compiladores.Cuando se habla de autómata, nos referimos a máquinas (abstractas o no) que sean capaces de computar. Las máquinas de Turing son un ejemplo de un autómata tan complejo que es capaz de resolver todos los problemas que una computadora actual puede resolver con precisión. Sin embargo, existen autómatas más simples que éstos, como los autómatas finitos o los autómatas de pila. Los autómatas finitos tienen relación con los lenguajes regulares y las expresiones regulares, mientras que los autómatas de pila tienen relación con los lenguajes y las gramáticas de contexto libre. Las expresiones regulares se usan en la actualidad para la búsqueda de patrones en textos, mientras que las gramáticas de contexto libre juegan un papel escencial en la implementación de compiladores.Cuando se habla de autómata, nos referimos a máquinas (abstractas o no) que sean capaces de computar. Las máquinas de Turing son un ejemplo de un autómata tan complejo que es capaz de resolver todos los problemas que una computadora actual puede resolver con precisión. Sin embargo, existen autómatas más simples que éstos, como los autómatas finitos o los autómatas de pila. Los autómatas finitos tienen relación con los lenguajes regulares y las expresiones regulares, mientras que los autómatas de pila tienen relación con los lenguajes y las gramáticas de contexto libre. Las expresiones regulares se usan en la actualidad para la búsqueda de patrones en textos, mientras que las gramáticas de contexto libre juegan un papel escencial en la implementación de compiladores.Cuando se habla de autómata, nos referimos a máquinas (abstractas o no) que sean capaces de computar. Las máquinas de Turing son un ejemplo de un autómata tan complejo que es capaz de resolver todos los problemas que una computadora actual puede resolver con precisión. Sin embargo, existen autómatas más simples que éstos, como los autómatas finitos o los autómatas de pila. Los autómatas finitos tienen relación con los lenguajes regulares y las expresiones regulares, mientras que los autómatas de pila tienen relación con los lenguajes y las gramáticas de contexto libre. Las expresiones regulares se usan en la actualidad para la búsqueda de patrones en textos, mientras que las gramáticas de contexto libre juegan un papel escencial en la implementación de compiladores.Cuando se habla de autómata, nos referimos a máquinas (abstractas o no) que sean capaces de computar. Las máquinas de Turing son un ejemplo de un autómata tan complejo que es capaz de resolver todos los problemas que una computadora actual puede resolver con precisión. Sin embargo, existen autómatas más simples que éstos, como los autómatas finitos o los autómatas de pila. Los autómatas finitos tienen relación con los lenguajes regulares y las expresiones regulares, mientras que los autómatas de pila tienen relación con los lenguajes y las gramáticas de contexto libre. Las expresiones regulares se usan en la actualidad para la búsqueda de patrones en textos, mientras que las gramáticas de contexto libre juegan un papel escencial en la implementación de compiladores.Cuando se habla de autómata, nos referimos a máquinas (abstractas o no) que sean capaces de computar. Las máquinas deTRANSCRIPT
-
Introduccin
Cuando se habla de autmata, nos referimos a mquinas (abstractas o no) que sean
capaces de computar. Las mquinas de Turing son un ejemplo de un autmata tan
complejo que es capaz de resolver todos los problemas que una computadora actual
puede resolver con precisin. Sin embargo, existen autmatas ms simples que stos,
como los autmatas finitos o los autmatas de pila.
Los autmatas finitos tienen relacin con los lenguajes regulares y las expresiones
regulares, mientras que los autmatas de pila tienen relacin con los lenguajes y las
gramticas de contexto libre. Las expresiones regulares se usan en la actualidad para
la bsqueda de patrones en textos, mientras que las gramticas de contexto libre
juegan un papel escencial en la implementacin de compiladores.
Conceptos
Gramticas formales.-
Las gramticas formales son sistemas de manipulacin simblica que permiten generar
cadenas de smbolos, llamadas por estobien formadas, o bien reconocer cundo una
cadena dada est, en efecto, bien formada. En este primer captulo, meramente
introductorio, ilustraremos con varios ejemplos estos tipos de sistemas e inclusive
algunos otros sistemas un tanto ms generales.
Jerarqua de Chomski en Autmatas.-
Tipo Nombres Tipo de autmata
reconocedor
0 Irrestricta Mquinas de Turing
1 Irrestricta con
memoria limitada
Mquinas de Turing con
cinta acotada
2 Sensibles al contexto
con borro
Mquinas de Turing con
dominio total
3 Sensibles al contexto
no reductivas
Mquinas de Turing con
``espacio lineal''
4 Libres de contexto Autmatas de pila no-
deterministas
-
5 Libres de contexto
deterministas
Autmatas de pila
deterministas
6 Lineales Autmatas lineales
7 Regulares Autmatas regulares
Automatas.-
Los autmatas vienen a ser mecanismos formales que "realizan" derivaciones en
gramticas formales. La manera en que las realizan es mediante la nocin de
reconocimiento. Una palabra ser generada en una gramtica si y slo si la palabra
hace transitar al autmata correspondiente a sus condiciones terminales. Por esto es
que los autmatas son analizadores lxicos (llamados en INGLS "parsers") de las
gramticas a que corresponden.
Autmata finito.-
Un autmata finito (determinista) es pues una estructura de la forma
donde
Se construyen a partir de un conjunto de estados Q y de un conjunto de smbolos de
entrada T. Su funcionamiento queda determinado por una funcin de
transicin . Sit(q,s)=p esto se interpreta como que el autmata transita
del estado q al estado p cuando arriba el smbolo s. En todo autmata finito se cuenta
con un estado inicial, y un conjunto de estados finales .
Autmata no-determinista.-
Los autmatas no-deterministas se conforman como los autmatas finitos, salvo que
sus transiciones, en lugar de ser funciones, son relaciones que a cada pareja
(estado,estmulo) le asocian varios, uno o ningn estado.
Tiene una estructura de la forma donde