Notas de clase. Teoría de la computación. Lenguajes, autómatas, gramáticas

Más vistas

Notas de clase. Teoría de la computación. Lenguajes, autómatas, gramáticas

Libro Impreso

Disponibilidad: No Disponible


Categoría: Informática

Editorial: Universidad Nacional de Colombia

Universidad Nacional de Colombia

Año de Edición: 2004

2004

ISBN: N.D.

N.D.

Facultad: Facultad de Ciencias

Sede: Bogotá


La colección Notas de Clase de la Facultad de ciencias es un espacio abierto a los profesores para publicar su experiencia docente recopilada en el tiempo a través de notas escritas. Se espera que las interrelaciones autor-colegas y profesores-estudiantes sea la mejor manera para que estas notas s...
Más Información
COP $ 19.000
Producto no disponible para la venta temporalmente

SKU: 353

Producto creado el 06/01/2005

description~Descripción~pv

Detalles

La colección Notas de Clase de la Facultad de ciencias es un espacio abierto a los profesores para publicar su experiencia docente recopilada en el tiempo a través de notas escritas. Se espera que las interrelaciones autor-colegas y profesores-estudiantes sea la mejor manera para que estas notas se depuren a fin de que en un futuro mediato adquieran carátula de texto.
additional~Información adicional~pv

Información adicional

Editor / MarcaUniversidad Nacional de Colombia
CiudadBogotá
FacultadFacultad de Ciencias
Año de Edición2004
Número de Páginas222
Idioma(s)Español
Alto y ancho17 x 24
Peso0.3700
Tipo Productolibro
custom_attributes_author~Autor~pv

Rodrigo De Castro

información no disponible.

custom_attributes_toc~Tabla de Contenido~pv

Prólogo
Introducción. ¿Qué es la teoría de la computación?

1. Alfabetos, cadenas y lenguajes

Alfabetos y cadenas
Concatenación de cadenas
Potencias de una cadena
Longitud de una cadena
Reflexión o inversa de una cadena
Subcadenas, prefijos y sufijos
Lenguajes
Operaciones entre lenguajes
Concatenación de lenguajes
Potencias de un lenguaje
La clausura de Kleene de un lenguaje
Reflexión o inverso de un lenguaje
Lenguajes regulares
Expresiones regulares

2. Autómatas finitos

Autómatas finitos determinalistas (AFD)
Diagrama de transiciones de un autómata
Diseño de autómatas
Autómatas infinitos no-determinalistas (AFN)
Equivalencia computacional entre los AFD y los AFN
Autómatas con transiciones ? (AFN – ?)
Equivalencia acomputacional entre los AFN – ? y los AFN
Teoría de Kleene. Parte I
Ejemplos de la parte I del Teorema de Kleene
Lema de Arden
Teorema de Kleene. Parte II
Ejemplos de la parte II del teorema de Kleene

3. Otras propiedades de los lenguajes regulares

Lema de bombeo
Propiedades de clausura
Propiedades de clausura para autómatas
Homomorfismos +
Imagen inversa de un homomorfismo +
Algoritmos de decisión

4. Lenguajes y gramáticas independientes del contexto
Gramáticas generativas
Gramáticas independientes del contexto
Árbol de una derivación
Gramáticas ambigüas
Gramáticas para lenguajes de programación
Gramáticas para lenguajes naturales +
Gramáticas regulares
Eliminación de las variables inútiles
Eliminación de las producciones ?
Eliminación de las producciones unitarias
Forma Normal de Chomsky (FNC)
Forma normal de Greibach (FNG) +
Lema de bombeo para LIC
Propiedades de clausura de los LIC
Algoritmos de decisión para G y C

5. Autómatas con Pila

Autómatas con Pila Deterministas (AFPD)
Autómatas con Pila no Deterministas (AFPN)
Aceptación por pila vacía
Autómatas con Pila y LIC. Parte I
Autómatas con Pila y LIC. Parte II +

6. Máquinas de Turing

Máquinas de Turing como aceptadoras de lenguajes
Subrutinas o macros
Máquinas de Turing como calculadoras de funciones
Máquinas de Turing como generadoras de lenguajes
Variaciones del modelo estándar de MT
Simulación de autómatas por medio de máquinas de Turing
Autómatas con dos Pilas (AF2P)+
Propiedades de clausura de los lenguajes RE y de los lenguajes recursivos
Máquina de Turing, computadores, algoritmos y la tesis de Church-Turing

7. Problemas indecidibles

Codificación y enumeración de máquinas de Turing
Máquinas de Turing universal
Algoritmos de aceptación para lenguajes RE
Lenguajes que no son RE
Lenguajes RE no recursivos y problemas indecidibles o irresolubles

Bibliografía

reviews~Reseñas~pv