Cursos

Home

1112034 Lenguajes y Autómatas 

GRUPO  CCB01

TRIMESTRE 15I

Comentarios y sugerencias

cbarron@correo.azc.uam.mx

cbarron99@hotmail.com

1. Plática de los temas del curso. Lenguajes, sintaxis y semántica. Diferencias entre las oraciones: 1) Cual es su nombre. 2) "Cual" es su nombre. 3) ¿Cual es su nombre? Tarea 1.
2. Modo de evaluación. Posible acuerdo: 3 exámenes parciales por el 80% y 30% de tareas, proyectos, reportes y participación (promedio del parcial). $ P_p=(P_1+P_2+P_3)/3 $. Calificación Final = $ (P_p+E_g+1(Apuntes))/2 $. Escala: (0,6)-NA, [6,7.5)-S, [7.5-8.5)-B y [8.5,11] MB. $E_g$ Largo si reprobaste un parcial. Corto si los apruebas. Presentación del contenido del curso: 1. Estructuras ordenadas: arreglos, tuplas, listas, pilas, colas, cadenas y lenguajes. 2. Autómatas finitos y expresiones regulares. 3. Lenguajes regulares y no regulares. 4. Gramáticas libres de contexto. 5. Autómatas con pila. 6. Lenguajes de contexto libre y lenguajes que no son de contexto libre. 7. Máquinas de Turing. 8. Tesis de Church-Turing. 9. Lenguajes enumerables recursivamente.
3. Teoría Axiomática de Conjuntos (Lectura 2, Paul Halmos). Definición de un Alfabeto $\Sigma$. $\phi$ conjunto vacío. $\ni$ símbolo nulo y su justificación.
4. Solución Tarea. Tuplas, producto cruz y proyección. Especificación formal de Autómata Finito Determinístico: $AF$=($q_0$, $Q$,$F$,$\Sigma$,$\delta$) donde $q \in Q$, $Q$ conjunto finito de estados, $F \subset Q$, $\Sigma$ Alfabeto finito de símbolos, $\delta: Q \times \Sigma \to Q$ función de transición.
5. Demostración y explicación del simulador de Autómatas Finitos Determinísticos en Matlab. En clase, se explicó y se mostró como funciona el simulador con el autómata de la clase anterior que detecta números pares. Los alumnos desarrollaron el ejemplo de un autómata que detecta la cadena 111 (de tres unos) y no importa lo que tenga antes o después.  Lo diseñaron mediante un diagrama de transiciones y luego definieron la tabla de estados finales y la tabla del AFD. Se escribieron los archivos y se realizaron algunas pruebas. Correctez es que un AFD debe funcionar para lo que fue especificado, de otra forma es incorrecto. Si solo se realizan algunas pruebas, el programa funciona para estas pruebas pero no es necesariamente correcto. La correctez debe ser una prueba lógica que abarque o sea exhaustiva de todos los casos posibles.
6. Definición de $\Omega_{\Sigma}$. $x\in \Omega_{\Sigma}$, $|x| $ denota la longitud de una cadena $x$. Sea $s \in \Sigma$ entonces $sx$ es una cadena (concatenación). Dado un AFD = $(q_0,\Sigma, Q, F, \delta)$, se define la función de transición para cadenas $\widehat{\delta}: Q \times \Omega_{\Sigma} \to Q$ de forma recursiva. Finalmente, el lenguaje de un autómata AFD es L(AFD)=$\{ x\in \Omega_{\Sigma}   \,| \, \widehat{\delta}(q_0,x)\in F \}$.
7. Dudas tarea 4.
8. Motivación y definición del Autómata Finito Nodeterministico  AFN=$(q_0,\Sigma, Q, F, \delta_N)$ donde $\delta_N: Q \times \Sigma \to 2^Q.$
9. Lunes 30 de septiembre. Construcción de $\widehat{\delta}_N$ $:2^Q  \times \Omega_{\Sigma} \to 2^Q$ y  L(AFN)=$\{ x\in \Omega_{\Sigma}   \,| \, \widehat{\delta}_N(\{q_0\},x) \cap F \neq \emptyset \}$. Prop. Dado un AFD, existe un AFN tal que L(AFD)=L(AFN).
10.  Construcción de $\widehat{\delta}_\ni$ $:2^Q  \times \Omega_{\Sigma} \cup \{\ni\}\to 2^Q$ y  L(AFN$\,_{\ni}$)=$\{ x\in \Omega_{\Sigma}   \,| \, [ \widehat{\delta}_\ni(\{q_0\},x)]_\ni \cap F \neq \emptyset \}$. Donde $[q]_\ni$ es la clase de todos los estados relacionados con $q$ mediante una transición $\ni$.
11. Prop. Dado un AFN=$(q_0,\Sigma, Q, F, \delta_N)$, existe un AFN$\,_{\ni}$ tal que L(AFN)=L(AFN$\,_{\ni}$). Expresiones regulares (ER) y su álgebra bajo las operaciones $+$ y concatenación.  Cerradura de Kleene ($\mathbf{s} ^*$). Reglas para construir un AFN$\,_{\ni}$ dada una ER.
12. Clase de ejercicios.
13. 1er. examen parcial.
14. Viernes 11 de octubre. Solución del 1er. examen parcial. Revisión de exámenes y tareas.

1. Teorema de Kleene. Dada una ER existe un AFD (AFN y AFN$\,_{\ni}$) tal que ER=L(AFD) y recíprocamente el lenguaje de un AFD  (AFN y AFN$\,_{\ni}$) es una ER. Motivación el lenguaje de los paréntesis apareados no corresponde a una ER. Necesidad de hacer explicita la prioridad en las expresiones de suma y producto, mediante el uso de paréntesis. Tipo de servicio: Ultimo que entra primero que sale. Estructura de datos Pila: funciones modificadoras: creación, push(obj), pop(). Funciones observadoras: es_vacia(). Componentes de un Autómata de pila determinístico y no determinístico. APD=($q_0$, $Q$,$\Sigma$,P,$\delta$) y APN=($q_0$, $Q$,$\Sigma$,P,$\delta_N$) donde $P$ es una pila, $\delta$ $:2^Q  \times \Omega_{\Sigma}\times Oper(Pila) \to Q$ y $\delta_N$ $:2^Q  \times \Omega_{\Sigma}\times Oper(Pila) \to 2^Q$ respectivamente ($Oper$ es abreviatura de operaciones).
2. La visión de los lenguajes (y los autómatas) como resultado aún no explicado de los Mundos del Doctor Popper. Construcción del AFPD para el lenguaje de {(),(()),((())), ...}. Mapa de la situación actual para describir las transiciones del AFP: Estado, pila, cadena por leer  $\vdash$ (lo que sigue) Estado, pila, cadena por leer o $\ni$. Convención para que un AFPD o un AFPN acepte una cadena: debe terminar de leerla, con la pila vacía y sin fallos en las operaciones de pila.
3. Ejemplo. Definición de $\vdash*$ y del lenguaje de un autómata de pila. Diseño de un  L(AFPD$\,_{\ni}$) para el lenguaje L={aA, bB, cC, abBA, acCA, abcCBA, bacCAB, aaabBAAA,...}. Ejemplos de cadenas aceptadas y cadenas rechazadas mapas de memoria o situación. Sugerencias para Tareas 8 y 9. Se acuerdan las fechas de entrega de las tareas 7,8 y 9.
4. Repaso. Maquinas y funciones versus Sintaxis y gramáticas. Introducción a las gramáticas. Notación BNF. G=(<I>,$\Sigma$,M,R) donde <I>$\in$ M meta-símbolo inicial, $\Sigma$ alfabeto de símbolos terminales, M conjunto de meta-símbolos y R conjunto de reglas en BNF. Las gramáticas sirven para reconocimiento (de una cadena de símbolos terminales a <I> por medio de aplicar las reglas de derecha a izquierda) o para generación del lenguaje (de <I> a cadenas de terminales por medio de aplicar las reglas de derecha a izquierda). Árboles de sintaxis. Una gramáticas es ambigua si una cadena tiene dos árboles de sintaxis. Una gramática es independiente del contexto o libre de contexto si todas sus reglas tiene un meta-símbolo del lado derecho y del lado izquierdo cadenas de Meta-símbolos y símbolos terminales.  Ejemplos: Gramática no ambigua, gramática ambigua y gramática para expresiones aritméticas: L={a,b,a+b,a*b,a*b+a,a+b*a,...}.

5. Ejercicios de gramáticas para 1) Lenguaje vacio $\phi$, 2) Lenguaje del símbolo nulo  {$\ni$}, 3) Lenguaje de la ER a, 4) Lenguaje de la ER a*, 5) Lenguaje de los paréntesis anidados, {$(^k)^k\,|\,k \geq 1$}. Los ejemplos muestran que las gramáticas son capaces de generar lenguajes de regulares y libres de contexto que son incluso los lenguajes que reconocen los autómatas de pila.

6. Ejercicios.

7. 2do examen parcial.

1. Recapitulación Maquinas y estructuras gramaticales. Explicación de la equivalencia entra la Máquina de Turing y la Máquina de Von Newman. Codificación de una MT. La MT universal, la MT que lle una codificación de una MT para imitar el funcionamiento de la MT codificada.
2. MT universal y MT con múltiples cintas. Ejemplos de como las MT determinan Lenguajes. Prop. No existe una MT que determine que toda MT se detiene.
3. Viernes 15 de noviembre de 2019. No hay clase.
4. MT con estados finales, funciones recursivas, lenguajes enumerables como ejemplo de lenguajes decidibles.
5. Viernes 22. Repaso del curso para preparar Examen Final.