Cap 1: Introducci´n a los aut´matas o o Tutores: Luis Antonio Chamba Eras Edison Leonardo C...
Introducci´n o • Estudio de las m´quinas abstractas. a ...
Introducci´n o • Estudio de las m´quinas abstractas. a • D´cada de los 30’, Alan Turin...
Introducci´n o • Estudio de las m´quinas abstractas. a • D´cada de los 30’, Alan Turin...
Introducci´n o • Estudio de las m´quinas abstractas. a • D´cada de los 30’, Alan Turin...
Introducci´n o • 1969, S.Cook amplio estudio de Turing, separ´ los problemas ...
Introducci´n o • 1969, S.Cook amplio estudio de Turing, separ´ los problemas ...
Introducci´n o • 1969, S.Cook amplio estudio de Turing, separ´ los problemas ...
Porqu´ estudiar la teor´ de aut´matas? e ıa o • Existen varias razones del estudio de la teor´...
Porqu´ estudiar la teor´ de aut´matas? e ıa o • Existen varias razones del estudio de la teor´...
Porqu´ estudiar la teor´ de aut´matas? e ıa o • Existen varias razones del estudio de la teor´...
Porqu´ estudiar la teor´ de aut´matas? e ıa o • Existen varias razones del estudio de la teor´...
Introducci´n a los aut´matas finitos o o • AF son modelos utiles para diferentes tipos de hardware y ...
Introducci´n a los aut´matas finitos o o • AF son modelos utiles para diferentes tipos de hardware y ...
Introducci´n a los aut´matas finitos o o • AF son modelos utiles para diferentes tipos de hardware y ...
Introducci´n a los aut´matas finitos o o • AF son modelos utiles para diferentes tipos de hardware y ...
Introducci´n a los aut´matas finitos o o • AF son modelos utiles para diferentes tipos de hardware y ...
Introducci´n a los aut´matas finitos o o • Existen muchos sistemas o componentes que pueden encontrar...
Introducci´n a los aut´matas finitos o o • Existen muchos sistemas o componentes que pueden encontrar...
Introducci´n a los aut´matas finitos o o • Existen muchos sistemas o componentes que pueden encontrar...
Introducci´n a los aut´matas finitos o o • Existen muchos sistemas o componentes que pueden encontrar...
Representaciones estructurales • Gram´ticas y Expresiones Regulares. a ...
Representaciones estructurales • Gram´ticas y Expresiones Regulares. a • Gram´ticas: son modelos utiles en ...
Representaciones estructurales • Gram´ticas y Expresiones Regulares. a • Gram´ticas: son modelos utiles en ...
Aut´matas y complejidad o • Importante para el estudio de los l´ ımites de la...
Aut´matas y complejidad o • Importante para el estudio de los l´ ımites de la...
Aut´matas y complejidad o • Importante para el estudio de los l´ ımites de la...
Bibliograf´ ıa [1] John E. Hopcroft, Rajeev Motwani y Jeffrey D. Ullman Teor´ de Aut´matas, lenguajes y ...
of 28

Porque estudiar la teoría de autómatas

Transparencias de apoyo para la Unidad de Lenguajes Formales y Teoría de
Published on: Mar 4, 2016
Source: www.slideshare.net


Transcripts - Porque estudiar la teoría de autómatas

  • 1. Cap 1: Introducci´n a los aut´matas o o Tutores: Luis Antonio Chamba Eras Edison Leonardo Coronel Romero Carrera de Ingenier´ en Sistemas ıa Universidad Nacional de Loja Septiembre 2012 1 / 28
  • 2. Introducci´n o • Estudio de las m´quinas abstractas. a 2 / 28
  • 3. Introducci´n o • Estudio de las m´quinas abstractas. a • D´cada de los 30’, Alan Turing estudio una m´quina abstracta, e a con las capacidades de los ordenadores actuales. 3 / 28
  • 4. Introducci´n o • Estudio de las m´quinas abstractas. a • D´cada de los 30’, Alan Turing estudio una m´quina abstracta, e a con las capacidades de los ordenadores actuales. • Turing, l´ ımites de lo que una m´quina de c´lculo pod´ o no a a ıa pod´ hacer. ıa 4 / 28
  • 5. Introducci´n o • Estudio de las m´quinas abstractas. a • D´cada de los 30’, Alan Turing estudio una m´quina abstracta, e a con las capacidades de los ordenadores actuales. • Turing, l´ ımites de lo que una m´quina de c´lculo pod´ o no a a ıa pod´ hacer. ıa • 40’ y 50’, estudiaron los aut´matas finitos (AF), propusieron o para modelar funcionamiento del cerebro. • Finales 50’, N. Chomsky inicio el estudio de las Gram´ticas a Formales. 5 / 28
  • 6. Introducci´n o • 1969, S.Cook amplio estudio de Turing, separ´ los problemas o que se pod´ resolver de forma eficiente mediante la ayuda de ıan un ordenador de los que al principio pueden resolverse pero en la pr´ctica consumen tanto tiempo que los ordenadores se vuel- a ven in´tiles para todo excepto para casos simples del problema u (insolubles)(NP-dif´ıciles). 6 / 28
  • 7. Introducci´n o • 1969, S.Cook amplio estudio de Turing, separ´ los problemas o que se pod´ resolver de forma eficiente mediante la ayuda de ıan un ordenador de los que al principio pueden resolverse pero en la pr´ctica consumen tanto tiempo que los ordenadores se vuel- a ven in´tiles para todo excepto para casos simples del problema u (insolubles)(NP-dif´ıciles). • Conceptos de AF y GF, se emplean para el dise˜o y construcci´n n o de software. 7 / 28
  • 8. Introducci´n o • 1969, S.Cook amplio estudio de Turing, separ´ los problemas o que se pod´ resolver de forma eficiente mediante la ayuda de ıan un ordenador de los que al principio pueden resolverse pero en la pr´ctica consumen tanto tiempo que los ordenadores se vuel- a ven in´tiles para todo excepto para casos simples del problema u (insolubles)(NP-dif´ıciles). • Conceptos de AF y GF, se emplean para el dise˜o y construcci´n n o de software. • Los conceptos de la M´quina de Turing, nos ayuda a compren- a der lo que esperamos de nuestro software. • La teor´ de problemas intratables nos permite deducir si po- ıa dremos enfrentarnos a un problema y escribir un programa para resolverlo o encontrar alguna manera de abordar el problema: hallar una aproximaci´n, m´todo heur´ o e ıstico o alg´n m´todo pa- u e ra limitar el tiempo que utilizar´ el programa para resolverlo. a 8 / 28
  • 9. Porqu´ estudiar la teor´ de aut´matas? e ıa o • Existen varias razones del estudio de la teor´ de aut´matas ıa o dentro de las Ciencias de la Computaci´n. o 9 / 28
  • 10. Porqu´ estudiar la teor´ de aut´matas? e ıa o • Existen varias razones del estudio de la teor´ de aut´matas ıa o dentro de las Ciencias de la Computaci´n. o • Introducci´n a los aut´matas finitos. o o 10 / 28
  • 11. Porqu´ estudiar la teor´ de aut´matas? e ıa o • Existen varias razones del estudio de la teor´ de aut´matas ıa o dentro de las Ciencias de la Computaci´n. o • Introducci´n a los aut´matas finitos. o o • Representaciones estructurales. 11 / 28
  • 12. Porqu´ estudiar la teor´ de aut´matas? e ıa o • Existen varias razones del estudio de la teor´ de aut´matas ıa o dentro de las Ciencias de la Computaci´n. o • Introducci´n a los aut´matas finitos. o o • Representaciones estructurales. • Aut´matas y complejidad. o 12 / 28
  • 13. Introducci´n a los aut´matas finitos o o • AF son modelos utiles para diferentes tipos de hardware y soft- ´ ware. 13 / 28
  • 14. Introducci´n a los aut´matas finitos o o • AF son modelos utiles para diferentes tipos de hardware y soft- ´ ware. • SW para dise˜ar y probar el comportamiento de curcuitos digi- n tales. 14 / 28
  • 15. Introducci´n a los aut´matas finitos o o • AF son modelos utiles para diferentes tipos de hardware y soft- ´ ware. • SW para dise˜ar y probar el comportamiento de curcuitos digi- n tales. • Analizador L´xico, separa el texto de entrada de en unidades e l´gicas: identificadores, palabras reservadas, signos de puntua- o ci´n, etc. o 15 / 28
  • 16. Introducci´n a los aut´matas finitos o o • AF son modelos utiles para diferentes tipos de hardware y soft- ´ ware. • SW para dise˜ar y probar el comportamiento de curcuitos digi- n tales. • Analizador L´xico, separa el texto de entrada de en unidades e l´gicas: identificadores, palabras reservadas, signos de puntua- o ci´n, etc. o • SW para explorar cuerpos de texto largos, como colecciones de p´ginas web o para determinar el n´mero de apariciones de a u palabras, frases u otros patrones. 16 / 28
  • 17. Introducci´n a los aut´matas finitos o o • AF son modelos utiles para diferentes tipos de hardware y soft- ´ ware. • SW para dise˜ar y probar el comportamiento de curcuitos digi- n tales. • Analizador L´xico, separa el texto de entrada de en unidades e l´gicas: identificadores, palabras reservadas, signos de puntua- o ci´n, etc. o • SW para explorar cuerpos de texto largos, como colecciones de p´ginas web o para determinar el n´mero de apariciones de a u palabras, frases u otros patrones. • SW para verificar sistemas que tengan un n´mero de estados fi- u nitos diferentes, como protocolos de comunicaci´n o protocolos o seguros de intercambio de informaci´n. o 17 / 28
  • 18. Introducci´n a los aut´matas finitos o o • Existen muchos sistemas o componentes que pueden encontrar- se siempre en uno de una serie de estados finitos. 18 / 28
  • 19. Introducci´n a los aut´matas finitos o o • Existen muchos sistemas o componentes que pueden encontrar- se siempre en uno de una serie de estados finitos. • El prop´sito del estado es el de recordar la parte relevante del o historial del sistema. 19 / 28
  • 20. Introducci´n a los aut´matas finitos o o • Existen muchos sistemas o componentes que pueden encontrar- se siempre en uno de una serie de estados finitos. • El prop´sito del estado es el de recordar la parte relevante del o historial del sistema. • Existe un n´mero finito de estados, generalmente es imposible u recordar el historial completo por lo que el sistema debe di- se˜arse cuidadosamente, con el fin de recordar lo que es m´s n a importante y olvidar lo que no es. 20 / 28
  • 21. Introducci´n a los aut´matas finitos o o • Existen muchos sistemas o componentes que pueden encontrar- se siempre en uno de una serie de estados finitos. • El prop´sito del estado es el de recordar la parte relevante del o historial del sistema. • Existe un n´mero finito de estados, generalmente es imposible u recordar el historial completo por lo que el sistema debe di- se˜arse cuidadosamente, con el fin de recordar lo que es m´s n a importante y olvidar lo que no es. • Ventaja de disponer de un n´mero finito de estados es que u se puede implementar el sistema mediante un conjunto fijo de recursos. 21 / 28
  • 22. Representaciones estructurales • Gram´ticas y Expresiones Regulares. a 22 / 28
  • 23. Representaciones estructurales • Gram´ticas y Expresiones Regulares. a • Gram´ticas: son modelos utiles en el dise˜o de software que sir- a ´ n ve para procesar datos con una estructura recursiva, un ejemplo es el Analizar Sint´ctico (parser) que se ocupa de las funcio- a nes anidadas recursivamente de los lenguajes de programaci´no como expresiones aritm´ticas, condicionales, etc. (E— E + E) e 23 / 28
  • 24. Representaciones estructurales • Gram´ticas y Expresiones Regulares. a • Gram´ticas: son modelos utiles en el dise˜o de software que sir- a ´ n ve para procesar datos con una estructura recursiva, un ejemplo es el Analizar Sint´ctico (parser) que se ocupa de las funcio- a nes anidadas recursivamente de los lenguajes de programaci´no como expresiones aritm´ticas, condicionales, etc. (E— E + E) e • Expresiones regulares: especifican la estructura de los datos es- pecialmente de la cadenas de texto, los patrones de cadenas que pueden definir las expresiones regulares son los mismos que pueden ser descritos por los aut´matas finitos, el estilo es dife- o rente al de las gram´ticas ([A-Z][a-z]*[ ][A-Z][A-Z]). a 24 / 28
  • 25. Aut´matas y complejidad o • Importante para el estudio de los l´ ımites de la computaci´n. o 25 / 28
  • 26. Aut´matas y complejidad o • Importante para el estudio de los l´ ımites de la computaci´n. o • Qu´ puede hacer una computadora? Decidibilidad, Decidibles e 26 / 28
  • 27. Aut´matas y complejidad o • Importante para el estudio de los l´ ımites de la computaci´n. o • Qu´ puede hacer una computadora? Decidibilidad, Decidibles e • Qu´ puede hacer una computadora de manera eficiente? Intra- e tabilidad, Tratables (funci´n crezca lentamente en funci´n a los o o par´metros de entrada-funciones polin´micas). a o 27 / 28
  • 28. Bibliograf´ ıa [1] John E. Hopcroft, Rajeev Motwani y Jeffrey D. Ullman Teor´ de Aut´matas, lenguajes y computaci´n ıa o o Pearson, 2008. 28 / 28

Related Documents