2025-2026 Q2
10 de febrero de 2026
Al final de cada clase, cada uno de vosotros dirá o bien un tema que recuerde de esta clase o hará una pregunta.
Importante
Aseguraos de que podéis iniciar sesión en RACSO; si no, enviad un correo a ilario.bonacina@upc.edu
usuario: el mismo que en la FIB
contraseña: DNI sin letra
Es faran a l’aula B4 002.
La computación es el proceso de evolución de algún entorno, mediante una secuencia de pasos “simples y locales”.
– Avi Wigderson (Math and Computation)
Problemas con respuesta Sí/No
¿Cuáles son problemas de decisión?
Habéis visto muchos tipos de datos:
enteros, números en coma flotante, vectores, grafos, código de otros programas, …
Todos ellos pueden codificarse como cadenas de caracteres.
Los caracteres que eliges determinan el alfabeto.
. , _\}: ...___...0, 1\}: 1010, 1, 2 ,3 ,4 ,5 ,6 ,7 , 8 , 9, +, - , ( , )\}: (1+2)-3a , b, c\}: aaabbbccc¡El alfabeto no debe ser vacío ni infinito!
Cualquier conjunto finito (no vacío) puede tomarse como un alfabeto. Normalmente los alfabetos se denotan por \Sigma.
Concatenaciones finitas de caracteres (o símbolos) de \Sigma son palabras (o cadenas).
\Sigma^* = el conjunto de todas las palabras sobre \Sigma
¿Es \Sigma^* finito?
¿Tiene w\in \Sigma^* la propiedad lógica P?
¿Es w\in \{x\in \Sigma^* \mid P(x)\}?
El estudio de los subconjuntos de \Sigma^* es lo mismo que estudiar problemas de decisión.
Un lenguaje sobre \Sigma es cualquier subconjunto de \Sigma^*.
¿Cuántos de los siguientes son lenguajes sobre \Sigma?
\emptyset (el conjunto vacío)
\{\lambda\}
\Sigma^*
\lambda
\lambda (o \epsilon) = la palabra vacía
w=s_1s_2\cdots s_n, u=t_1t_2\cdots t_m
(donde cada s_j,t_i\in \Sigma)
pueden ser concatenadas y dan la palabra
w\cdot u = wu = s_1s_2\cdots s_n t_1t_2\cdots t_m
(exponenciación) w\in \Sigma^* \begin{align*} w^0&=\lambda\\ w^{n+1}&=w^n\cdot w \end{align*}
w es una subpalabra de u si \exists x,y\in \Sigma^*, u=xwy
La longitud de w=s_1s_2\cdots s_n (donde cada s_i\in \Sigma) es |w|=n.
para palabras u,w\in \Sigma^*, |w|_u = número de apariciones de u en w como subpalabra.
(reverso) w^R = lo mismo que w pero con los símbolos escritos en orden inverso
\Sigma=\{0,1\}. L=\{w\in \Sigma^* \mid w \text{ es palíndromo}\}
¿Cómo escribir esto formalmente?
Para todo x,y,w\in \Sigma^*,
L\cdot M = \{x\cdot y \mid x\in L \land y\in M\}
¿Es la concatenación conmutativa?
¿Cuál es el elemento neutro de la concatenación?
L\cdot \emptyset= ?
(exponenciación) L^0=\{\lambda\}, L^{n+1}=L^n\cdot L
(estrella de Kleene) L^*=\bigcup_{n\in \mathbb N}L^n
(más de Kleene) L^+=\bigcup_{n\geq 1}L^n
Para comprobar: la estrella de Kleene de \Sigma es el conjunto de todas las palabras sobre \Sigma.
En otras palabras, hemos usado * con dos significados distintos, pero esto está bien.
Las próximas semanas nos centraremos en estudiar \mathbf{REGULAR}.
\forall A,B\in \Sigma^*\quad AL_1\subseteq B L_2 \implies A\subseteq B \tag{2}
PS 0 – Exercici 2 (Concatenació — propietats bàsiques)
PS 0 – Exercici 3 (Estrella de Kleene — propietats bàsiques)