Cursos

Home

1112034 Lenguajes y Autómatas 

GRUPO  CCB81

TRIMESTRE 13O

Comentarios y sugerencias

cbarron@correo.azc.uam.mx

cbarron99@hotmail.com

1. Presentación curso, objetivos y forma de evaluación. Acuerdos: Tarea 1. 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.

2.  Estructuras ordenadas: cadenas, lenguajes. Notación de conjuntos y tuplas. Conjuntos por extensión o lista de elementos, $ A= \{ a, b, c\} $, ejemplo de un conjunto incorrecto $ \{ a , a\} $. Conjuntos por regla: $ B = x \in \Omega | P(x) } $ (para repasar este punto Lectura: Conjuntos de Paul Halmos). Resumen clase.

3. Autómata finito determinístico, AFD = $ (Q, q_0, \Sigma, \delta, F)$. Diagrama de transición de estados, tabla de la función de transición $\delta$, función de transición extendida $\hat{\delta} $, L(AFD) =$ \{ w \in \Sigma^* |  \hat{\delta} (q_0,w) \in F \}$. Ejemplos: Autómata finito determinístico para el lenguaje de números impares en binario. Autómata finito determinístico para $L_p= \{ papa \}$.

4. Repaso y explicación del enfoque del curso de Lenguajes y Autómatas. Estudio de lenguajes. Lenguaje: conjunto de cadenas sobre un alfabeto. Formas de estudio: por su estructura (sintaxis y gramáticas) y por mecanismos o funciones. Un ejemplo por estructura: Expresiones Regulares. Un ejemplo por funciones: Autómata Determinístico Finito, AFD = $ (Q, q_0, \Sigma, \delta, F)$. Desarrollo en clase del diseño del AFD de la tarea 2. Todos tienen -5 hasta que entreguen correctamente la tarea 2. La lectura 6 (Jerarquía de Chomsky: Wikipedea y una Presentación), les reforzará el enfoque del curso.

5. Expresiones Regulares.

6. Autómata finito no determinístico (AFN). Introducción al Teorema de Kleene.

7. Autómata finito no determinístico con transiciones $ \varepsilon $ (AFN-$ \varepsilon $).

8. Ejemplos de AFN-$ \varepsilon$. Teorema de Kleene. Lenguajes regulares y no regulares. Algunos de los ejercicios de tarea. Teorema del bombeo. Construcción de un (AFN-$ \varepsilon $) para cualquier expresión regular.

9. Construcción por el método del conjunto potencia de estados de un AFD equivalente (que acepta el mismo lenguaje) a un AFN.

10. Huelga.

11. Examen.

1. Revisión de la 1era etapa del curso. Teorema de Kleene. Equivalencia entre los lenguajes de las expresionas regulares y los lenguajes de AFD, AFN y AFN-$ \varepsilon $.
2. Gramáticas, notación BNF. $ G=(T, N, R,<S>) $ donde $ T $: conjunto de símbolos terminales, $ N $: conjunto de metasímbolos o símbolos no terminales denotados por $<nombre>$, $ R $: conjunto de reglas en notación BNF y  $<S> \in N$: metasímbolo de arranque.   Reconocimiento y derivación de las palabras del lenguaje de una gramática. Caso de estudio: Gramática libre de contexto y recursiva para el lenguaje no regular $ L= \{ (^k)^k \, |\, k =1, 2, 3, \ldots \} = \{ (), (()), ((())), \ldots \}$.
3. Estructura de Pila como cadenas. Autómata de pila (AP) (de Barrón), $ \Sigma$ es un conjunto arbitrario finito o infinito. Ejemplos de  reconocimiento de cadenas y de construcción de los diagramas de la función de transición no determinística de un AP para los lenguajes $ L_1= \{ (^k)^k \, |\, k =1, 2, 3, \ldots \} $ = $ \{ (), (()), ((())), \ldots \}$,  $ \{ a^k b^k | k =1, 2, 3, \ldots \}$, $ \{ a^{2k} b^k | k =1, 2, 3, \ldots \}$ y $\{ w w^R | w \in \Sigma^* \ \{ \varepsilon \} $(palindromes)$ \}$. Donde $w^R$ es la palabra reflejada, por ejemplo, $w=abcbd$ entonces $w^R = dbcba$.  Derivacion $ s\omega \, q; P \vdash \omega \, r; P $ donde $ s \in\Sigma, \omega \in \Sigma^*,$  $q, r \in Q $ (Estados), $P: pila $.
4. Ejemplos de AP.
5. Los APD (Autómatas de Pila Determinísticos) forman una clase de lenguajes contenida propiamente en la clase de lenguajes de los AP.  Explicación basada en $ L_3 = L_1 \cup L_2,$ donde $L_1 = \{ a^kb^k | \, k=1,2,3, \ldots \}$ y $L_2 = \{ a^{2k}b^k | \,  k=1,2,3, \ldots \}$.
6. Equivalencia entre los lenguajes de las GIC recursivas y los lenguajes de los AP. Desarrollo de una gramática para $L_3$ de la clase anterior.
7. Máquina de Turing. Estando en un estado lee un símbolo, luego cambia de estado, escribe y se mueve. Función de transición $ \delta: Q \times \Sigma \to Q \times \Sigma \times \{I, D, H\} $ donde I y D son movimientos, I: Izquierda, D: derecha y H: detenerse (Halt). MT que calcula el siguiente número natural.  MT que calcula la suma de dos números positivos. MT que copia una cadena.
8. Formalización de la MT = $ (Q,\Sigma,\delta). $ MT para el lenguaje $\{ a^kb^kc^k |\, k=1, 2, 3, \ldots \}$. Lenguajes Libres del contexto y lenguajes sensitivos al contexto.
9. 2do examen parcial.
10. Solución 2do examen parcial.

1. (Lunes 21 de octubre) Computabilidad, Decibilidad. Tesis de Church-Turing.
2. (Miércoles 23 de octubre) No hay clase.
3. No hay alumnos. Oscar avisó que no va a asistir.
4. Computabilidad, indecibilidad, numeración de Gödel. Cap. 9 del libro Introducción a la Teoría de Autómatas, lenguajes y Computación, Hopcroft, Motwani, Ullman.
5. Funciones recursivas primitivas, lenguajes recursivamente enumerables, lenguajes enumerables. Ejemplos.
6. 3er Examen parcial.
7. No hay clase viernes 8 de noviembre.
8. 11 de noviembre, resolución y entrega de exámenes.