Problemas, Lenguajes y Algoritmos

Problemas, Lenguajes y Algoritmos (digital)

atálogo da Coleção CLE

Verifique a disponibilidade para aquisição desse volume impresso >>aqui<<

“Esta segunda edición es fruto de la experiencia de los autores en el dictado de diversos cursos de Lenguajes Formales y Autómatas y de Computabilidad y Complejidad en la Universidad Nacional de La Plata y en la Universidad Tecnológica Nacional, Regional La Plata, Argentina.

En cuanto a los contenidos, se han modificado los capítulos 1 y 2 afiadiendo ejemplos detallados, reescribiendo y profundizando algunos puntos e introduciendo algunas secciones nuevas. Se describirán brevemente las modificaciones.

En el capítulo 1, en primer lugar se ha agregado la sección 1.3 sobre las formas normales de Chomsky y de Greibach para lenguajes libres de contexto. Con respecto a los autómatas finitos y expresiones regulares, se ha subdividido y ampliado la sección correspondiente. En 1.4, además de los autómatas finitos determinísticos y no determinísticos, se tratan los que admiten movimientos 4. En 1.5 se estudia la equivalencia de los lenguajes reconocidos por autómatas finitos con los lenguajes regulares. La sección 1.6, que es nueva, trata el teorema de Myhill-Nerode que asocia una relación de equivalencia a un lenguaje dado, permitiendo decidir si existe o no un autómata finito que lo reconozca. La demostración es constructiva y en ella se define, si existe, el autómata mínimo que reconoce tal lenguaje. Se introducen las redes de Petri que son un instrumento útil para modelizar procesos concurrentes (1.9). Se estudian aquí brevemente los lenguajes asociados a tales redes y su relación con las familias de lenguajes de la jerarquía de Chomsky.

En el capítulo 2, en la sección 2.3, se agrega la demostración del Ilamado “pumping lemma” para el caso de los lenguajes de tipo 2 y 3. Ese resultado se aplica al análisis de cuatro problemas de decisión que se relacionan con lenguajes: el de pertenencia (probar que existe un algoritmo que lo resuelva equivale a probar la recursividad del tipo de lenguaje), el de comprobar si un lenguaje asociado a cierto autóômata o gramática es vacio o no, O bien si es finito o infinito y por último el de determinar si dos gramáticas dadas generan o no el mismo lenguaje. En la sección 2.5 se agrega un ejemplo de problema relativo a conjuntos de alcanzabilidad de Redes de Petri, que resulta indecidible reduciéndolo al décimo problema de Hilbert.

Los capítulos 3 y 4 presentan sólo cambios tipográficos respecto de la edición anterior.

Se incluyen también tres apéndices, cuyo autor es mi colega y amigo el Dr. Guillermo Martínez, a quien agradezco mucho su valiosa colaboración en sus dos facetas: la de matemático especialista en lógica por una parte y la de escritor y crítico literario por otra.

El primero de los tres apéndices es el resumen de un cursillo que dictó en la Universidad Nacional del Sur (Bahía Blanca, Argentina) sobre computabilidad, complejidad y teoremas de Gódel. Se profundiza aquí sobre el significado de nociones y resultados que son básicos en el contenido de este libro. El segundo y el tercero son transcripciones de comentarios de libros aparecidas en diarios de Bs. As. À través de su crítica sobre el libro El último teorema de Fermat, de Simon Singh, Martinez narra la historia del teorema de Fermat y la consecuente develación de su misterio. Asimismo, el comentario de la última edición de Leyendo a Euclides, del eminente matemático italiano Bepo Levi, da pie para explicar a lectores no necesariamente matemáticos la “estética” de los sistemas axiomáticos y su relación con la noción de incompletud de Gódel.

En cuanto a la forma del libro, se han modificado tipos de letras, títulos y secciones y se han rehecho los dibujos de los capítulos 1 y 2.”

Marta Sagastume

Gabriel Baum

Con la colaboración de Guillermo Martínez

Volume 37 – 2003

ISSN: 0103-3147

Segunda Edição, 2003

Índice para catálogo sistemático

Linguagem de programação (Computadores) 005.13

Lógica simbólica e matemática - Processamento de dados 005.131