Cursos

Home

1112034 Lenguajes y Autómatas 

GRUPO  CCB81

TRIMESTRE 14P

Comentarios y sugerencias

cbarron@correo.azc.uam.mx

cbarron99@hotmail.com

1. Presentación del curso, modo de valuación y primera tarea.
2. Acordamos horario de asesoría. Repaso: Conjuntos (Ver lectura 2. Teoría Intuitiva de conjuntos). Axioma de extensión. Axioma de especificación. Notación, identitdad de elementos, operadores $ \in $, $ \subset $, = (igualdad de conjuntos), conjunto potencia, cardinalidad, función. Recordatorio de combinaciones, permutaciones, binomio de Newton, números naturales. Ejemplo de Proposición y demostración, ejemplo de funciones discretas entre dos conjuntos D (dominio), R (rango o contradominio). Para conjuntos finitos, $|2^\Omega| = 2^{| \Omega |}.$
3. Viernes 25/04/2014, asistencia 3 de 7. Faltaron los que no entregaron tarea 1. Entrega de la tarea 1, revisada. Tuplas, motivación acerca de las estructuras ordenadas como lenguaje formal para la definición de sistemas y modelos de computación y matemáticas. Explicación de la equivalencia entre tuplas y conjuntos. Producto cruz. Introducción a cadenas, símbolo nulo, alfabeto, longitud de cadenas, $\Sigma^0, $ $\Sigma^1, $ $\Sigma^2, $ ..., $\Sigma^n. $
4. Tarea. Lunes, 28 de abril. Asistencia 6 de 7. Repaso, tuplas, cadenas y lenguajes. Listas. Definición y ejemplos de ER. Tarea 2 para todos.
5. Solución tarea 2. Ejemplos de ER. Desarrollo de la habilidad del alumno de verificar su respuesta o resultado. Sugiero revisar y realizar los ejercicios del libro recomendado: Teoría de Autómatas, Lenguajes y Computación del tema de ER (capítulo 3).
6. Viernes. Asistencia 5. Algebra ER. Idempotencia de   la cerradura de Kleen.  Limites de las ER. Introducción a los Autómatas Finitos Determinísticos (AFD).
7. Miércoles. Asistencia 5. No entregaron la tarea del AFD para $L_1 .$ Se resolvió la tarea 3. Definición de $ \vdash ,$ $ \vdash^\ast $, $ \dashv ,$ $\dashv ^\ast. $ Recordatorio de Inducción Matemática (IM). Definición mediante IM de la función $ \widehat{\delta} , $ extensión de la función de transición $ \delta $ de un AFD a cadenas.
8. Viernes. Se recibió la tarea. Lema del bombeo. Ejemplos y explicación por Inducción Matemática. Tarea 5 para el lunes.
9. Resolución de la tarea 5. Autómata Finito No deterministico (AFN). Conversión de un AFD en un AFN. Construcción del AFD equivalente a un AFN por el Método de la Potencia. Tarea 6.
10. Miércoles. Resolución de la tarea 6. Ejemplo completo de equivalencia entre una AFN y un AFD. Explicación de como demostrar que los lenguajes del AFN y AFD son equivalentes mediante Álgebra de ER.
11. Examen para casa: 1er. Examen Parcial. Un alumno puede dar la clase para excentar 1er examen. Construcción de la extensión a cadenas de la función $ \widehat{\delta_N} , $ por IM.
12. Solución del Examen.
13. Equivalencia entre los AFN y los AFN$ -\varepsilon $ (paralelismo y demonios tipo Unix). Teorema de Kleene.  Los lenguajes regulares o L $ _{0}$ son equivalentes a los que generan o reconocen los autómatas ADF, AFN, AFN$ -\varepsilon $.
    
    
     

1. Repaso de los dos modos de estudiar lenguajes:  Estructural y funcional. Introducción al Autómata de Pila (Barrón, Como programa la naturaleza).
2. Autómata de Pila, AP=(Q, q $ _{0}$, P, O, $\delta_{p}$) donde Q : Conjunto de estados; q $ _{0}$ : estado inicial; P: pila, O: conjunto universal de objetos (no necesariamente finito), $\delta_{p}$ : función no determinística del autómata de pila.
3. La asistencia bajo a 4 de 5. Recordatorio de uso y referencia de conceptos, abstracción y metalenguajes. Estudio estructural de lenguajes por gramáticas. G=(S, V, <I>, R) donde S: Conjunto de símbolos o palabras terminales; V: Conjunto de variables o metasímbolos (<nombre>); <I> $ \in$ V: Metasímbolo inicial y R: Conjunto de reglas en formato BNF.  Ejemplos. Generación y reconocimiento de un lenguaje usando una gramática. Hacer la tarea 9.
4. La asistencia bajo a 3 de 5. Gramáticas. Resolución de la tarea 9. Gramáticas libre de contexto, recursividad y ambigüedad. Ejemplos. El caso de los palíndromes y de las expresiones aritméticas con paréntesis, suma y resta son posibles temas de examen. Por favor asistan, porque los temas son diferentes y tienen un grado de dificultad mayor a los del inicio.
5. Lunes 2 de junio, no hay clase.
6. Miércoles 3 de junio. Introducción a la Máquina de Turing.
7. Maquina de Turing. Ejemplos. Tarea 11. Abajo están las asignaciones de los artículos.
8. Ejemplos de Máquinas de Turing. La suma de dos números. Computabilidad desde el punto de vista de una MT. Ejemplos a desarrollar: división de números positivos, determinación si un número es primo.
9. Entrega de Tarea para el segundo parcial viernes 13 de junio. O podemos cambiarla la fecha de entrega para el lunes, siempre que alguno desarrolle un justificación y alguno de los ejemplos que se dejaron la clase anterior. A las 17:39 no había alumnos. A las 17:45 se presentó un Miguel, o sea, un alumno de cinco.
10. Lunes. Máquina Universal de Turing (MUT). La computabilidad no es decidible por una MUT. Por favor me explican su conducta de porqué faltan a clases.
11. Segundo Examen Parcial.

1. Lenguajes Recursivos Enumerables.
2. Funciones Recursivas, Funciones recursivas primitivas.
3. Teorema de Gödel, Los números reales no son enumerables (Diagonal de Cantor).
4. Enumeración de Cantor y Técnica Diagonalde Cantor. Clasifcación de lenguajes por grámaticas: Independientes del contexto, dependientes del contexto, generales. Clasificación de Lenguajes por máquinas.
5. Decibilidad. Prop. L(R)  $\Leftrightarrow \overline{L(R)}$.  Prop. LD $ \in $ L(RE). Prop. LU $ \in$ L(NO_RE) donde LD:  Lenguaje Diagonal;  LU: Lenguaje Universal.
6. Tercer Examen Parcial.