Download Automatas y Lenguajes PDF

TitleAutomatas y Lenguajes
File Size1.8 MB
Total Pages214
Table of Contents
                            Preliminares
	Conjuntos
		Operaciones
		Operaciones con conjuntos
		Equivalencias de conjuntos
		Relaciones y funciones
		Conjuntos infinitos
	Manejo lógico de enunciados
		Tablas de verdad
	Pruebas por inducción
	Lenguajes
		Alfabeto, cadena de caracteres
		Lenguajes, operaciones con lenguajes
	La jerarquía de Chomsky
	Ejercicios
I Lenguajes regulares y sus máquinas
	Autómatas finitos
		Modelado de sistemas discretos
			Estados finales
		Máquinas de estados finitos
			Funcionamiento de los autómatas finitos
		Definición formal de autómatas finitos
		Métodos de diseño de AFDs
			Diseño por conjuntos de estados
			Diseño de AFD por complemento
		Equivalencia de autómatas finitos.
		Simplificación de Autómatas finitos
			Tabla de estados distinguibles
			Simplificación por clases de equivalencia
		Autómatas finitos con salida
			Máquinas de Moore
			Máquinas de Mealy
			Equivalencia de las máquinas de Moore y Mealy
			Cálculo de funciones en AF
		Autómatas finitos no deterministas
			Representación formal de los AFN
			Diseño de AFN
			Equivalencia de AFD Y AFN
			Más diseño de AFN: Intersección de lenguajes
		Ejercicios
	Expresiones Regulares y Gramáticas Regulares
		Lenguajes Regulares
			Definición formal de Lenguajes Regulares
		Expresiones regulares
			Significado de las ER
			Metodología de diseño de las ER
			Equivalencias de Expresiones Regulares
		Límites de las representaciones textuales
		Equivalencia de expresiones regulares y autómatas finitos
			Conversión de ER a AF
			Conversión de AF a ER
		Gramáticas regulares
			Gramáticas formales
			Gramáticas regulares
			Autómatas finitos y gramáticas regulares
		Limitaciones de los lenguajes regulares
			El teorema de bombeo
		Ejercicios
II Lenguajes libres de contexto y sus máquinas
	Gramáticas y lenguajes libres de contexto
		Gramáticas y la jerarquía de Chomsky
		Lenguajes y gramáticas libres de contexto (LLC y GLC)
		Formalización de las GLC
		Diseño de GLC
			Adaptación de GLC
			GLC para unión de lenguajes
			Mezcla de gramáticas
			GLC para la concatenación de lenguajes
		Arboles de derivación
			Ambigüedad en GLC
			Derivaciones izquierda y derecha
		Pruebas de corrección y completez
		Gramáticas libres y sensitivas al contexto
		Transformación de las GLC y Formas Normales
			Eliminación de reglas A
			Eliminación de reglas AB
			Eliminación de reglas inaccesibles
			Formas Normales
		Limitaciones de los LLC
			Teorema de bombeo para los LLC
		Propiedades de decidibilidad de los LLC
		Ejercicios
	Autómatas de Pila
		Funcionamiento de los Autómatas de Pila (informal)
		Diseño de AP
			Combinación modular de AP
		Formalización de los AP
		Relación entre AF y AP
		Relación entre AP y LLC
		Compiladores LL
			Principio de previsión
		Compiladores LR(0)
		Ejercicios
III Máquinas de Turing y sus lenguajes
	Máquinas de Turing
		Funcionamiento de la máquina de Turing
		Formalización de la MT
			Configuración
			Relación entre configuraciones
			Configuración ``colgada''
			Cálculos en MT
			Palabra aceptada
		MT para cálculos de funciones
		Problemas de decisión
			Relación entre aceptar y decidir
		Tesis de Church
			Comparación de las MT con otras máquinas
		Máquinas de Post
			Formalización de las MP
			Equivalencia entre MP y MT
		Límites de las MT
			El problema del paro de MT
		MT en la jerarquía de Chomsky
		Ejercicios
                        

Similer Documents