- Presentación del curso, modo de valuación y primera tarea.
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.
- Estructuras Ordenadas: tuplas, listas, cadenas y
lenguajes. Repaso de Conjuntos. Axioma de extención y axioma de
selección. Formas de demostración que usaremos en el curso. Conjunto
vacío ($\phi $) . Cardinalidad. Conjunto Potencia ($P(A)$ o $ 2^A $) .
Repasar por su cuenta álgebra de Conjuntos y leyes de Morgan.
-
Asistentes.
Conjuntos Ordenados: Producto cruz, tuplas. Cadenas como tuplas
simplificadas si "(,",", ")". Alfabeto ($\Sigma $) conjunto finito de
símbolos. Símbolo nulo $\varepsilon $. Longitud de una cadena
($\left\vert c\right\vert $): número de caracteres de la cadena en un
alfabeto. Nota $\varepsilon $ $\notin $ $\Sigma $ y $\left\vert
\varepsilon \right\vert $ = 0. Cerradura de Kleene, $\Sigma ^{\ast
}=\Sigma ^{0}+\Sigma ^{1}+\Sigma ^{2}\ldots $. Donde $\Sigma ^{0}$=
{$\varepsilon$ }. Ejemplo de un ADF y tarea 3.
-
Asistentes.
Resolución de tarea 3. Entrega y recomendaciones de redacción sobre la
tarea 1. Definición de un AFD y concepto de estado. Ejemplo de un
robot.
- Definición de un AFD. Conjunto de estados finito,
alfabeto, función de transición (usar una tabla para verificar que es
función). Explicación de porque Q y $ \Sigma $ son finitos.
Complejidad de la función de transición. Autómatas con salida, Mealy y
Moore. Ejemplos: Complemento de un bit, versión Mealy y Moore.
Autómata que juega gato
(programa en C, se compila con
Dev-CPP),
tabla de la función de
transición del autómata que juego gato.
- Introducción al Teorema de Kleene. AFD,
contrucción de la función de transición para cadenas: $\widehat{\delta
} $ $ : $ $ Q\times \Sigma ^{\ast }$ $ \rightarrow Q $ por Inducción
Matemática. Convención: las cadenas se separan de derecha a izquierda,
o sea, $cs$ donde $c \in \Sigma^* $ y $ s \in \Sigma$. $L\left( AFD\right)
$ $ =$ $ \{ c \in $ $ \Sigma ^{\ast }$ $| $ $ \widehat{\delta }\left(q_{0},c\right)
\in F \}.$ Autómata Finito No Determinístico (AFN). Características:
paralelismo, corutinas, etc. Usos en Sistemas Operativos, Bases de
Datos, Computación paralela e intensiva. Un AFN salta a un
conjunto de estados dado un par $ (q,s)$ $ \in $ $ Q \times \Sigma $.
Construcción del árbol de derivación ($\vdash $). Ejemplo de una
función de transición no determinística ( $ \delta _{N}: $ $ Q \times
\Sigma $ $ \rightarrow 2^{Q}, $ donde $ 2^{Q} $ es el conjunto
potencia de $ Q ). $
- Prop. Dado un AFD construir un AFN, tal que L(AFD)
$\subset $ L(AFN). Prop. Dado un AFN construir un AFD, tal que L(AFN)
$\subset $ L(AFD). (Demostración por método de la potencia sobre Q).
Ejemplos. Reflexión sobre el número de estados de un AFD y la longitud
de cadenas. Lema del Bombeo: Si un AFD acepta una cadena de longitud
mayor o igual al número de estados, entonces acepta un lenguaje
infinito.
-
1er examen
parcial.
|
- Resolución del 1er examen parcial.
-
Nota para subir calificación:
Los que tienen 4 o más de calificación, deben entregar:
1er examen parcial
y tareas. T1: ¿Que fundamenta el estudio de los Lenguajes y Autómatas? T2:
Opcional Repasar conjuntos. T3: Igualdad entre dos conjuntos que representan
los Números Naturales. T4: Autómata para llegar a su silla. Los que tienen menos de 4, todo lo anterior y la
Guía para el primer examen parcial. Entregar viernes 3 de octubre.
-
Repaso y recordatorio: Reflexiones, introducción y
ejemplos del AFN-$\varepsilon$. Derivación de cadenas, similitud en la
construcción de las funciones de transición de cadenas de los AFD ($\widehat{\delta
}$ Inducción Matemática), de los AFN ($\widehat{\delta}_N $, Inducción
Matemática) y de los AFN-$\varepsilon$ ($\widehat{\delta}_{\varepsilon}$,
Inducción Matemática, clases de equivalencia de estados:$\varepsilon$-clausura(q))
. Prop. Dado un AFN construir un AFN-$\varepsilon$, tal que L(AFN)
$\subset $ L(AFN-$\varepsilon$).
-
Prop. Dado un AFN-$\varepsilon$ construir un AFN, tal que L(AFN-$\varepsilon$)
$\subset $ L(AFN). Ejemplos de derivación de un AFN-$\varepsilon$ y
del uso de $\widehat{\delta}_{\varepsilon}$. Expresiones Regulares (ER).
Definición, ejemplos. Machotes para números naturales con repetición y sin
repetición, números enteros, palabras de 3 silabas, nombre de variable en
Fortran, construcción del respectivo AFD o AFN para ER. (Lex y análisis
Lexicográfico de compiladores: separación de un texto en tokens o machotes).
-
Prop. Dado un AFD, su lenguaje se puede representar por una
ER. Prop. Dada una ER, se construye un AFN-${\varepsilon}$ tal que acepte la
ER como su lenguaje. Fin del Terema de Kleene: Los AFD, AFN, AFN-${\varepsilon}$
y las ER generan lenguajes equivalentes (Lenguajes Regulares o $ L_{0} $).
Los Autómatas con salida generan lenguajes Regulares. Prop. Cualquier
lenguaje finito es Regular. Prop. L={ $(^n$ $)^n$ | $n \geq 1$} no es
Regular. Demostración usando el Lema del Bombeo. O sea los ADF no pueden
"contar" que los paréntesis que abran sean iguales a los paréntesis que
cierran.
-
Automata de Pila (AP). Listas y Pilas, definiciones
autocontenidas. Operaciones de pila Push(p,o), pop(P), Tip(P). AP=(Q,$q_{0}$,P,
$\Sigma$,$\delta_{p}$). Ejemplo para L$_{()}$. Derivación para cadenas con
AP ($\vdash$, $\vdash ^{\ast }$.
-
L={$a^n b^n c^n$ | $n \geq 1$} no es aceptado por un AP.
Gramáticas. G=(T,<I>,M,R). Ejemplos derivación.
-
Grámatica para L$_{()}$. Introducción a la Máquina de Turing.
Para el examen: Teorema de Kleene. Funciones de transición de cadenas. Cap.
4 Propiedades de los lenguajes Regulares, Cap.5 Lenguajes y Gramáticas
independientes del contexto, y Cap. 6. Autómata de Pila del libro de
Teoría de Lenguajes y Computación. El examen $ P_2 $ será el
viernes 17 de octubre y se basa en las clases y ejercicios vistos.
-
2do. Examen Parcial.
|
-
2do. Examen. Resolución del 2do examen parcial.
Mis disculpas, por favor revisen sus calificaciones. NOTA: Tareas,
examen resuelto para subir calificación los aceptaré el viernes 24 de
octubre o si los envían antes por correo.
- Máquina de Turing Universal (MTU). Tesis de Church-Turing.
MTU y la indecibilidad de la computabilidad. Equivalencia entre los
Modelos de Von Newman y no Von Newman con la MT. Esta parte de la
clase es la base para que desarrollen la tarea 8.
- Sistemas Numéricos. Naturales, Enteros,
Racionales, Irracionales, Reales. Cardinalidad aleph cero y aleph 1.
Diagramas de sintaxis para verificar que los Naturales, Enteros y
Racionales son lenguajes regulares. Explicación del porque la
representación de los racionales por parte entera y mantisa no es
representable por modelos de máquina, 1) su alfabeto no es finito y 2)
inducen un error por el tamaño de la mantisa. La ER de los
racionales como cociente es exacta (cuando los números son listas de
dígitos) y es 0 + SN / N, donde N son los positivos y
S es el signo. En los reales existen problemas no computables.
Diagonal de Cantor. Numeración de Gödel. Introducción a los lenguajes
recursivos y recursivos enumerables. Funciones recursivas.
- Funciones computables. Resolución de problemas por
MT. Encontrar el n-ésimo numero primo. Ejemplos de funciones
recursivas con su correspondiente MT. Lenguajes recursivos y lenguajes
recursivos enumerables. Su relación con derivación y reconocimiento de
lenguajes con MTs. La función castor ocupado no es computable.
- Tres proposiciones: 1) Sea L1 recursivo, entonces
su complemente es recursivo. 2) L2 recursivo enumerable, entonces su
complemente es recursivo enumerable. 2) El lenguaje de la diagonal de
los lenguajes recursivos enumerables está fuera de los lenguajes
recursivos enumerables. El problema de la marca en la cinta infinita y
la MT, o porqué la tecnología de microprocesadores debe ser más rápida
y usar paralelismo.
- Examen oral del ensayo CISC, RSIC y MT. Alamilla,
Cabrera presentaron sus ensayo.
- Clasificación de lenguajes por sus reglas
gramaticales. La grámatica sensitiva al contexto de $L_{abc}=\{a^n b^n
c^n | n \geq \}$. Ejemplo de derivaciones.
|
