Cursos

Home

1112034 Lenguajes y Autómatas 

GRUPO  CCB81

TRIMESTRE 15P

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  y  proceso de evaluación. 3 exámenes parciales ($P_i$) por el 80% y 30% de tareas, proyectos, reportes y participación ($T_i$). $ C_i=P_i * 80% + T_i*30%, i=1,2,3$. Antes global, promedio: $ Pr = (C_1 + C_2 + C_3)/3$. Examen Global (corto ($E_g$) y largo, si reprobaste parciales). Los parciales recuperados modifican $P_i$ y la calificación parcial $C_i$. Calificación Final = $ (Pr+E_g)/2 $. Escala. (0,6):NA, [6,7.5): S, [7.5-8.5):B y [8.5,11]: MB. Todos presentan Examen Global y proyecto.
2. Clase 1.
3. Clase 2.
4. Autómata finito determinístico (AFD). Se construyó un robot que solo reconoce o ejecuta la cadena dccci. Concepto de estado, función de transición $(\delta :Q\times \Sigma \to Q)$  y diagrama de transición. Definición, ejemplos y L(AFD) [lenguaje de un autómata finito determinístico]. Se presentaron ejemplos que expresan como ER a los L(AFD). Lenguaje de los positivos con fracción. Lenguaje de los impares. 
5. Construcción de la función de transición para cadenas $\widehat{\delta }:Q\times \Sigma ^{\ast }\rightarrow Q$. Construir la ER, ejemplos de $\widehat{\delta }$. Introducción al AFN y a su $\widehat{\delta }_N$. Construcción por inducción matemática y ejemplos con $\Sigma =\left\{ u,z,0,1\right\} $ y $L_{1}=\{x\in $ $\Sigma^{\ast }|$ $x$ tiene de prefijo una vocal y al menos un dígito$\}$. Prop. Para cualquier AFD existe un AFN que acepta el mismo lenguaje.
6. No hay clase el 15 de mayo, día del maestro.
7. Lunes 18 de mayo, no voy al salón. Por favor resuelvan los ejercicios de la tarea en el salón. Les informo que acudí al el salón para ayudarlos en los ejercicios.
8. Lema del Bombeo. Prop. Para cualquier AFN, existe un AFD, tal que L(AFN)=L(AFD). Método de los subconjuntos o método del conjunto potencia de Q. Ejemplos.
9. Construcción de la función de transición para cadenas de un AFN $\widehat{\delta}_n :Q\times \Sigma ^{\ast }\rightarrow 2^Q$. El AFN$-\varepsilon$=(Q,$q_0$,$\Sigma$,$\delta_\varepsilon$,F). Prop. Cualquier AFN tiene un AFN$-\varepsilon$ que acepta el mismo lenguaje del AFN. Clausura de un estado. Construcción de la función de transición de cadenas $\widehat{\delta}_\varepsilon$. Ejemplos.
10. Prop. Todo AFN$-\varepsilon$ tiene un AFN que acepta el mismo lenguaje. Transcripción de las ER en AFN$-\varepsilon$. Teorema de Kleene y los lenguaje regulares. Autómatas con salida: Mealy y Moore. Ejemplo y equivalencia.
11. Ejercicios. Se entrega el 1er examen a los alumnos.
12. Viernes 29 de mayo. No hay clase. Por favor depositan sus exámenes por debajo de la puerta de mi oficina H116.
     

1. Revisión y entrega del primer examen parcial.
2. Gramáticas. Reconocimiento y derivación de un lenguaje. Árbol de Reconocimiento. Notación BNF. $L_{()}$ no es regular. Gramáticas ambiguas. Construcción de una gramática por medio del árbol de reconocimiento. Ejemplos de gramáticas para $ L_{()} $ y $L_a=\{a,a+a,a+a+a,\ldots\}$. G=(V,<I>,$\Sigma$,R).  L(G) = $ \{ x \in \Sigma^\ast $ | <I> $ {\equiv }^{\ast } x \} $ =  $\{x \in \Sigma^\ast$ | $x$
   ${\rightarrow }^{\ast }$ <I> $\}.$
    
3. Clasificación de gramáticas. Autómata de Pila. Ejemplo de un AP para L =$\{  (^k  )^k |  k\geq 1 \}$ y L=$\{ a^{2k} b^k| k \geq 1 \}$. Los AP reconocen $\{ a^{mk} b^k| k \geq 1 \}$ o $\{ a^{k} b^{mk}| k \geq 1 \}$. L=$\{ a^k b^k c^k | k \geq 1 \}$ no puede ser reconocido por un AP y se muestra que es reconocido por una gramática sensitiva al contexto.
4. Máquina de Turing. Ejemplo para L$_{abc}$. Funcionamiento: lee, escribe y se mueve a la izquierda (I) o a la derecha (D) o se detiene (H). El proceso de una MT: 1) Falla porque no hay transición; 2) Se detiene (H) con el resultado correspondiente; 3) No se detiene.
5. Maquinas de Turing para determinar los números primos. Ejemplos. MT que genera cada uno de los números 1,11,111, etc. MT que copia un número en una lista de numeros: *1*11*111*->numero copiado<-. Tarea. MT para la división de números positivos. MT de un comparador de números positivos.
6. Máquina de Turing de decisión. Computabilidad. MT computable o recursiva. Codificación tipo enumeración de Gödel de MT.  Máquina de Turing Universal (MTU) y MTU de decisión (MTUd). Lenguajes y MT. No existe una MTUd que determine la computabilidad de una MT. O sea el lenguaje  de la computabilidad está fuera del alcance las MT.
7. Ejercicios 24, 22 y 10 de la lista de ejercicios del segundo parcial.
8. Ejercicios de la lista de ejercicios del segundo parcial.
9. Segundo examen parcial.
    

1. Funciones recursivas primitivas. Máquinas de Turing recursivas o computables, lenguajes recursivos o decidibles. Tesis de Church-Turing. Ejemplo completo para el lenguaje de {1111}.
2. Funciones recusivas primitivas. Reusabilidad. Modelo de Von Newman. MT con multiples cintas. Construcción de problemas computables. El lenguaje de los números primos es computable. Equivalencias entre el Modelo de Von Newman y la MTU. La MTU resuelve sin limitaciones de memoria, una MTU al igual que el modelo de Von Newman maneja problemas y programa en la cinta de memoria. Ejemplos de problemas con "funciones" que no son computables.  Discusión de la comparación de las capacidades de resolución de problemas del modelo de Von Newman, la MTU y una persona.
3.  Lenguaje de la Diagonal. Funciones recursivas primitivas y lenguajes decidibles o recursivos. Codificación de Gödel. El lenguaje de la diagonal no tiene una MT que lo reconozca. Técnica diagonal de Cantor.
4. Lenguajes Recursivos o decidibles (RE), Lenguajes recursivos enumerables (REN), Lenguajes No-REN. Ubicación del Lenguaje Universal (codificación de todas las MT y cadenas, base de la construcción del lenguaje de la diagonal) es REN. Prop. Todo Lenguaje L recursivo tiene su complemento $\bar{L}$ (en $\Sigma^*$)  que es recursivo. Prop. LU es REN y no es recursivo. En No-REN tenemos Lenguaje de la diagonal y Lenguaje de la computabilidad. Ejemplos de diversos de casos en REN. Reflexiones acerca de la industria del software y los lenguajes RE, REN y No-REN. Una propuesta para paliar las modas, los ataques y los virus es fortalecer la ética y  la educación de las sociedades de los profesionales de la computación.  
5. Teorema de Rice. Lenguaje no vacío. Lenguaje vacío. Discusión de los temas, modelos, propiedades y sus características.
6. Repaso de los temas de la UEA. Ejercicios 4 y 1.a) Lista de ejercicios para el tercer examen parcial.
7. Ejercicios de la  Lista de ejercicios para el tercer examen parcial
8. Tercer examen parcial.