Return to home

1112024 TEORIA MATEMATICA DE LA COMPUTACION 

GRUPO  CCB81

TRIMESTRE 13P

Comentarios y sugerencias

cbarron@correo.azc.uam.mx

1. Presentación curso, objetivos y forma de evaluación. Falte por error en los horarios.
2. Presentación curso, objetivos y forma de evaluación. Tarea 1.
3. Expresiones y conjuntos regulares. Conjunto por extensión y conjunto por regla, conjunto potencia, cardinalidad, $\Sigma $ (Alfabeto), $ \phi $ (conjunto vacio), $\varepsilon $ (símbolo nulo), concatenación, expresiones regulares, Enunciado del Teorema de Kleene: Las expresiones regulares son reconocidas por autómatas finitos y viceversa.
4. Autómata determinístico finito (ADF). Lenguajes, contexto humano, cultural, regional, en el crecimiento humano. Lenguajes formales como conjuntos de cadenas. Autómata como un robot móvil que alcanza una meta (bajo condiciones especificas). $ ADF = (Q, q_0, f, F, \Sigma)$ donde Q conjunto de estados,  $\left| Q\right| < \infty $, $ q_0 \in Q$ estado inicial, $f:Q \times \Sigma \to Q$ función de transición, $ F\subset Q$ conjunto de estados finales,  $ \Sigma $ alfabeto.  $f$ descrita como diagrama de transición o como tabla.
5. Ejemplo de un ADF: paridad par de tres dígitos binarios, diseño, verificación de funcionamiento correcto por el método exhaustivo, su lenguaje como expresión regular (Diagrama del Teorema de Kleene, entre los lenguajes de las expresiones regulares y el lenguaje de los autómatas reconocedores: ADF, AFN (autómata finito no determinístico), AFN-$\varepsilon$ (autómata finito no determinístico con transiciones nulas).
6. L(ADF)=$\{ w \in \Sigma \|    \widehat{\delta }(q_{1},w)\in \Sigma \}$ donde  ADF=$(Q,q_1,\delta,F,\Sigma)$ $Q:$ conjunto de estados, $q_1 \in Q$, $\delta:Q \times \Sigma \to Q$ función de transición, $ F \subset Q$ conjunto de estados finales, $\Sigma$ un alfabeto. La función de transición extendida es $\widehat{\delta }:Q \times \Sigma^* \to Q $ dada por: (Paso base) $\widehat{\delta }(q, \varepsilon) = q; $  $\widehat{\delta }(q, s) = \delta(q,s) $  $s \in \Sigma$. (Paso inductivo) Dados $ s \in \Sigma $ y $w \in \Sigma^*$, $\widehat{\delta }(q, sw) = \widehat{\delta }( \delta ( q, s),w)$.  Teoerema 3.4. (Formalmente) L(ADF) se expresa como expresión regular.
7. Teorema de Kleene. Fin del tema de autómatas reconocedores de expresiones regulares. Autómata finito con salida: Autómata de Moore y Autómata de Mealy. (Mealy, Moore y ADF son equivalentes en procesar cadenas de entrada que sean expresiones regulares). Ejemplos de Lenguajes que no corresponden con expresiones regulares. $ L= \{ 1^n0^n | n \geq 1 \}$,    $L_2 =\{ 1^{m+n} = 1^m + 1^n | m,n \geq 1 \}$, motivación para el siguiente tipo de autómata, el autómata finito de pila.
8. Revisión de las tareas. Deben ser correctas y completas. Se les solicita repetirlas. Como reconocer un lenguaje como Expresión Regular. Lema del Bombeo: Dado ADF=$(Q,q_1,\delta,F,\Sigma)$, $|Q|=n$, si $w \in L(ADF)$, $|w| \geq n|$ entonces la cadenas $w_k=xy^kz \in $ L(ADF).

1. Martes 28 de mayo. 1er. examen parcial.
2. Revisión del 1er. examen parcial y tareas. Autómata de finito de pila.
3. Autómata universal de pila (de Barrón).
4. Gramáticas, Gramáticas independientes de contexto (GIC). Autómata de Pila con aceptación por pila vacía (AFP). Equivalencia: L(GIC)=L(AFP).
5. 2do Examen parcial. Introducción a la máquina de Turing.
6. Maquina de Turing. Capacidades de la Máquinas de Turing. La indecibilidad computacional y la MT. Ejemplos de como crear MT.
7. Enumeración de Gödel, numerabilidad, los reales son isomorfos al intervalo (0,1), biyeccion entre (0,1) y los reales. Ejemplo de la técnica diagonal de Cantor. Las MT son numerables. Existe un lenguaje ($L_d$, lenguaje diagonal que no es reconocido por una MT), una explicación de esto por por la enumeración de Gödel y la técnica diagonal de Cantor. Funciones Recursivas. El conjunto de las funciones recursivas iniciales. El conjunto de las funciones recursivas primitivas (RP). Las funciones recursivas primitivas son computables. Existe un lenguaje (Lenguaje diagonal computable) que no corresponde con ninguna función de RP, una explicación de esto por por la enumeración de Gödel y la técnica diagonal de Cantor. El modelo de Von Newman y las MT. Las MT no determinísticas son equivalentes a las MT determinsticas. ´Cápitulos 8 y 9 del libro Introducción a la Teoría de autómatas, lenguajes y computación, Hopcroft, Motwani, Ullman. Notas de  Funciones recursivas.