- Acuerdo de un horario de asesoría: Lunes y viernes
de 15:00 a 16:00 y miércoles de 13:00 a 14:00. Acuerdo del proceso de
evaluació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. Presentación del curso y primera tarea.
- ¿Porqué usar símbolos? ¿Hay algún resultado que
indique cuantos símbolos usar? Estructuras ordenadas:
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. El estudio de los lenguajes, para este curso, será mediante
el estudio de conjuntos de cadenas o palabras y en clase explicamos
porqué es suficiente.
- Estructuras ordenadas:
Notación de conjuntos, tuplas y Cadenas. Operaciones de cadenas.
Alfabeto $\Sigma$ conjunto finito de símbolos. Identificación de los
números reales con la recta numérica, como ejemplo de un conjunto que
no se puede describir por extensión (palabras), sin embargo la
representación con la recta numérica identifica cada numero con un
punto (como por extensión). Representación de las cadenas como n-adas
(elementos de producto cruz sin "(","," y ")" por tanto heredan la
posición y por eso las cadenas se identifican con una secuencia de
símbolos). $\Sigma^*$ =$\{ x | x$ es una cadena de símbolos de $\Sigma$
o es $\epsilon \}$ = $\cup_{i=0}^\infty \Sigma^i$, donde $\epsilon$
es el símbolo nulo y $\Sigma^i$ =$\Sigma \times$ $\ldots$ $\Sigma$ ($i-$veces).
Sea $x\in\Sigma^*$, la longitud de $x$ ($|x|$) es el numero de
carácteres de $x$. Nota: $|\epsilon|=0$ y $\Sigma^0$=$\{ \epsilon \}$.
Numerabilidad: Un conjunto Numerable es el que es finito o se puede
poner en correspondencia con los números naturales ($ \mathbb{N} $ =
$\{ 0, 1,2,3,...\} $). Número de Cantor o cardinalidad de $\mathbb{N}
$, $|\mathbb{N} |$ = $\aleph^0$ (Aleph cero). Son
numerables $ \mathbb{N} $, $\{ x \in \mathbb{N} | x$ es par $\}$, $ \mathbb{Z}
$ y $ \mathbb{Q}$ (Numeración diagonal de Cantor). Finalmente
se demostró que $\Sigma^*$ es numerable. Tesis de CBR por estudiar en
el curso: El lenguaje humano no es numerable (porque no se restringe a
algún $\Sigma^*$).
- El lenguaje humano no es numerable. Ejemplos con
base en la tarea de inteligencia, los lenguajes numerables, los
lenguajes de los programas determinísticos y no determinísticos
(evolutivos) son numerables. Los lenguajes que manejan o hacen los
autómatas y la máquina de Turing son numerables. Axioma de extensión.
Dos conjuntos son iguales, $A=B$ $\Leftrightarrow$ $A\subsetB$ $\wedge$
$B\subset A$.
- Autómatas finitos. Diseño=programación. Concepto
de estado, concepto de transición, funcionamiento, modelo gráfico y
modelo formal. Lenguaje de un autómata finito.
- Solución de la tarea del autómata para los
múltiplos de 4. Tipos de autómatas (con salida y sin salida). Ejemplo
del autómata para el juego del gato o tres en linea (tarea 4).
- Sea AFD=($Q,q_0,\Sigma, \delta, F$). Función de
transición de un AFD extendida a cadenas, $\widehat{\delta }$: $Q\times\Sigma^*$
$\rightarrow Q$. L(AFD)={$x\in\Sigma^*$ | $\widehat{\delta} (q_0,x)$
$\in$ $F$ }. Ejemplos.
- Faltó medio grupo. Descripción del Teorema
de Kleene e introducción a las Expresiones Regulares. Ejemplos de
problemas de este nivel de modelo de computación en áreas diversas:
Compiladores, Genética, SETI (Search for ExtraTerrestrial
Intelligence), artefactos de uso diario, etc. Justificación
de la importancia de lograr los objetivos del curso: Describir, interpretar e ilustrar
los modelos teóricos de cómputo. Describir los conceptos de lenguaje
formal y gramática. Reconocer y diferenciar las clases de lenguajes
formales asociadas con cada modelo teórico de cómputo.
- Autómata Finito No-Deterministico (AFN). Construcción y
verificación entre la gráfica de transición y la tabla de transición.
Demostración de complejidad exponencial. Propiedades: a un estado y un
símbolo corresponde más de un estado de respuesta (paralelismo y
simultaneadad). Derivación ($ \vdash $) para la verificación de
aceptación de cadenas. AFN = ( $ Q $, $ q_0 $, $ \Sigma
$, $ \delta_{N} $, $ F $), donde $ \delta_{N} $: $ Q \times \Sigma $
$\rightarrow$ $2^{Q}$. Proposición. Una AFD y un AFN son equivalentes en el
sentido de que L(AFD)=L(AFN) [que estudiaremos y que es parte
del Teorema de Kleene].
- Lunes (27 de enero) Construcción de la función de
transición de un AFN extendida a cadenas. $\widehat{\delta_N}$.
Definición formal de L(AFN) con $\widehat{\delta_N}$. Proposición.
Una AFD y un AFN son equivalentes en el
sentido de que L(AFD)=L(AFN). Metodo de la Potencia
para construir el AFD a partir de un AFN.
-
Ejercicios.
- Primer Examen Parcial. Se cancelo por ir al
médico.
- 3/feb/2015.
Primer Examen
Parcial.
|
- Notas del Curso
- Clase en video llamada, Google Hangouts. Miércoles 19, a la hora
del curso en el salón Audiovisual 2 del Centro de Cómputo.
Clase corregida
19-02-2014. Versión corta
clase.
- Ejemplo de un AFD,
máquina vendedora.
- Exámenes guía 13o:
1er.,
2do.,
3er.,
ex. global.
- Se reanudan las clases en el salón
a partir del miércoles 26 de febrero de 2014.
- Miércoles 26. Autómata no determinístico de
transiciones nulas (AFN-$ \epsilon $).
- No hay clase. No alcanzo a llegar a clase, hoy
viernes 28 de febrero.
- Lunes 3 marzo. Construcción de $\widehat{\delta_{\epsilon} }$: $Q\times\Sigma^*$
$\rightarrow 2^Q$. L(AFN-$\epsilon$ )={$x\in\Sigma^*$ | $\widehat{\delta_{\epsilon}}
(q_0,x)$ $\cap $ $\neq$ $F$ }. Continuación del ejemplo del pasado
miércoles. Teorema Kleene completo, reglas de conversión entre AFN
y AFN-$ \epsilon $ y de ER a AFN-$ \epsilon $.
L$_{0}$ es el lenguaje de mas bajo nivel y corresponde a las ER (en
forma esructural) y es el mismo para todos los autómatas AFD, AFN y AFN-$ \epsilon $
(en forma funcional o de máquina).
- Gramaticas recursivas para lenguajes L1. G=(T,V,R,<I>), donde T:
conjunto de símbolos terminales, V : conjunto de variables, R:
conjunto de reglas de derivación en formato BNF, <I> $\in $V, variable
o meta-símbolo de arranque o inicial. Derivación y Reconocimiento. L(G)
= { $x$ $\in$ T* | <I> ${\equiv }^\ast $ $x$ }.
Autómata de Pila, AP =(Q, $q_0$,T,P,$\delta_p$) donde Q: conjunto
finito de estados, $q_0$ $\in$ Q, estado inicial, T: conjunto de
objetos o símbolos (no necesariamente finito), P: pila, con
operaciones: push(P,s), pop(P) y top(P), s $\in$ T, $\delta_p$
: $Q\times$ T
$\rightarrow $ Q $\times$ {Operaciones de Pila}. L(AP) =
{ $x$ $\in$ T* | $q_0$, P=$\phi$ $x$ ${\rightarrow }^\ast
$ $r$, P=$\phi$, $\epsilon$ } donde $q_0$, $r$
$\in$ Q, procesa toda la cadena y sólo se acepta si termina con la
pila vacia. $L_{kk} $ = { $a^k $ $b^k$ | $k$ = $1, 2, 3,
...$ } no es regular. Se desarrolló su gramática y su AP. Otro
ejemplo de un lenguaje no regular: $L_{k2k $ = { $a^k $ $b^{2k}$ | $k$
= $1, 2, 3, ...$ }.
- Viernes 7 de marzo no hay clase.
- 2do.Examen Parcial. Lenguajes L0: ADF y ER, Lenguajes L1:
Gramáticas Recursivas Libre de Contexto y Autómata de Píla, Ejemplo
Lenguaje L3: { $a^k b^k c^k$ }.
|
|
