Cursos

Home

1112034 Lenguajes y Autómatas 

GRUPO  CCB01

TRIMESTRE 15I

Comentarios y sugerencias

cbarron@correo.azc.uam.mx

cbarron99@hotmail.com

1. Presentación del curso, modo de valuación y primera tarea. Acuerdos: un horario de asesoría (por establecer)  y  proceso de evaluación. 3 exámenes parciales por el 80% y 20% de tareas, proyectos, reportes y participación. $ P_p=(P_1+P_2+P_3)/3 $, $ T=(C_1+C_2+...+C_m)/m $, Antes global: $ C_P=P_p*80% + T*30% $. Ex.Global (corto y largo, si reprobaste parciales). Calificación Final = $ (C_p+E_g)/2 $. Escala: (0,6)-NA, [6,7.5)-S, [7.5-8.5)-B y [8.5,11] MB. Acuerdos: exento si promedio >= 8.5 y proyecto.
2. Los lenguajes como conjuntos de cadenas de símbolos. Repaso de Conjuntos (Leer lectura 2, Conjuntos Paul Halmos. Axioma de Extensión y Axioma de selección. Notaci{on de conjuntos, operadores de conjuntos $=,\subset, \in$. Proposiciones (forma funcional), procedimiento y costo computacional para verificar la igualdad de conjuntos, universo  de contexto ($\Omega$), alfabetos, tuplas (subconjuntos de un producto cruz de conjuntos) y cadenas.
3. Elementos y operaciones de las cadenas de los lenguajes. Lenguaje vacío, símbolo nulo $\varepsilon$, concatenación, prefijo, sufijos, cerradura de Kleene. Ejemplos de lenguajes. Prop. Existe un lenguaje universal. Explicación de ejemplos que no son lenguajes.
4. Estudio de los lenguajes por estructura (sintaxis y grámaticas) en contraposición por mecanismos o funciones. Las ER y los Autómatas finitos determinísticos, autómatas finitos no determinísticos y autómatas finitos no determinísticos $-\varepsilon$ (Teorema de Kleene, que veremos más adelante).  Expresiones Regulares. Definición y ejemplos de ER y de lenguajes que no son ER.
5. Repetición del concepto de Lenguaje. Entrega de las tareas y explicación de la respuesta de la tarea 3. Entrega de las tareas 2.
6. Autómata finito determinístico (AFD). Definición, ejemplos y L(AFD) [lenguaje de un autómata finito determinístico]. Se propuso la tarea 4, es opcional realizarla.
7. La función de transición para cadenas $\widehat{\delta }:Q\times \Sigma ^{\ast }\rightarrow Q$. Construcción por inducción matemática y ejemplos. Preguntas para reflexionar: ¿Que tipo de transiciones tiene un AFD para un diccionario (conjunto finito de palabras? ¿Que caracteriza a un AFD para un lenguaje infinito?
8. Prop. El lenguaje de un AFD es una ER. Lema del Bombeo. (Primera etapa del Teorema de Kleene: Son equivalentes los lenguajes de las ER y los AFD, AFN, AFN$-\varepsilon$ ).
9. Viernes 6, no hay clase.
10. Autómata Finito No determinístico. AFN=(Q,$q_0$,$\Sigma$, $\delta_N $,F). Prop. Para cualquier AFD, L(AFD) es reconocido por un AFN. Construcción de $\widehat{\delta}_N$. Ejemplos de uso de $\widehat{\delta}_N$, por ejemplo para la construcción de L(AFN)={$x\in\Sigma^*$| $\widehat{\delta}_N$($q_0$,$x$) $\cap $ F $\neq$ $\phi$}.
11. Primer examen parcial. Examen 1 y examen 2.
12. Resolución del 1er examen parcial y entrega de exámenes y calificaciones. Examen de recuperación. Leer punto 8 tareas y Notas.
     

1. Prop. Para cualquier AFN existe un AFD, tal que L(AFN)=L(AFD). Explicación por el método de la construcción de subconjuntos (método del conjunto potencia). Ejemplo y explicación de la equivalencia. Sección 2.3.5 Equivalencia de autómatas finitos deterministas y no deterministas.
2. Solución del examen de tarea. Respuesta de la pregunta 4. Introducción al Autómata finito no determinista con transiciones nulas, AFN-$\varepsilon$=(Q,$q_0$,$\Sigma$, $\delta_{\varepsilon} $,F). $\delta_{\varepsilon} $ $:$ Q$\times \left( \Sigma \cup \left\{ \varepsilon \right\} \right) \rightarrow 2^{Q}$. Paralelismo y espontaniedad (demonios del Sistema Operativo Linux). Ejemplo.
3. Tipos de proyectos que pueden realizar. Gráficas o digráficas isomorfas. $\varepsilo$-clausura. Prop. Dado un AFN-$varepsilon$, existe un AFN, tal que L(AFN)=LAFN-$varepsilon$). Paso base de la construcción de $\widehat{\delta}_{\varepsilon} $.
4. Revisión Teorema de Kleene. Construcción de $\widehat{\delta}_{\varepsilon} $. Ejemplo de una ER y su reconocimiento por un AFN-${\varepsilon}$ mediante $\widehat{\delta}_{\varepsilon} $.
5. Prop. Para toda ER, existe un AFN-${\varepsilon}$, tal que L(ER)=L(AFN-${\varepsilon}$). Método gráfico de construcción de un AFN-${\varepsilon}$ para una ER. Ejemplos.
6. Un punto de vista biológico de máquina. Un AFD es una máquina que solo hace para lo que se diseño. Adaptación y percepción como paradigmas de una máquina con una estructura de datos (templetes, George Gamov). Estructura abstracta de pila para objetos o símbolos. Introducción al Autómata de Pila para el lenguaje de las cadenas de paréntesis balanceados (que no puede ser reconocido por un AFD). 
7. AP, L(AP) lenguaje del AP. Gramáticas libres de contexto, lineal y recursiva para L$_{()}$. Se mostro un ejemplo de un AP y una gramática para  L$_{()}$. Árbol de reconocimiento, derivación. Lenguaje de los palíndromes. NOTA: Corrección del AP del lenguaje de los palíndromes.  Perea o Rebollar, por favor confirmen por email quien detecto este error para subir su calificación del primer parcial.
8. 4 de marzo, descanso obligatorio UAM-A.
9. Corrección del AP del lenguaje de los palíndromes. Lenguajes no reconocidos por un AP. Introducción a la máquina de Turing.
10. Construcción del MT para $L_{a^kb^k}$. Discusión del funcionamiento y de la corrección del proceso o algoritmo. Revisión de temas antes del segundo examen.
11. Segundo examen parcial. Ver tarea 10.
12. Solución del segundo examen parcial. Repaso de aspectos clave de las respuestas del examen.

1. MT, codificación de Gödel y Máquina Universal de Turing. La computabilidad no es determinable por una MT (Ejemplo de indecibilidad).
2. Computabilidad. Último teorema de Fermat. Problema Castor Ocupado (Busy Beaver). Determinar el número de castores trabajando (ocupados). Explicación de que este problema no es computable y una similitud o relación con sistemas operativos de multiprogramación. Panorama de las arquitecturas Von Newman y No Von Newman y la tecnología de microprocesadores y buses inteligentes, no hay prueba e que alguna sea la más eficiente. Sugerencia para casi todos: En lugar de proyecto, presentar en forma individual o en grupo notas de todo el curso, mismas que serán entregadas para revisarlas y que serán evaluadas con un examen oral adicional a los exámenes parciales y global.
3. Viernes 20 de marzo. MT para comparar dos números enteros positivos. Ejemplo completo desarrollado por los alumnos.
4. Lunes 23 de marzo. Lenguajes recursivos y lenguajes recursivos numerables (o enumerables). Tesis de Church-Turing. Funciones Recursivas primitivas. Ejemplo de una función recursiva primitiva con la serie de Fibonaci y la suma de dos números.
5. Prop. El complemento de un Lenguaje recursivo no numerable es numerable. Técnica Diagonal de Cantor. Concepto de conjunto numerable. Ejemplo los reales no son numerables. Preliminares para demostrar que el lenguaje Diagonal no es recursivo numerable.
6. Prop. El lenguaje Diagonal no es recursivo numerable. Ejemplos de Lenguajes recursivos y recursivos no numerables.
7. 3er. examen parcial: lunes, 30 de marzo  de 2015. Examen extra para recuperar calificación de la parte 1.

8. Miércoles 1 de abril de 2015. Entrega exámenes y deben entregar sus notas.