February 17, 2026
Q: Given L_1,L_2 such that \emptyset \subsetneq L_1\subseteq L_2\subseteq \Sigma^*, which of the following two implications are true? \forall A,B\subseteq \Sigma^*\quad A\subseteq B \implies AL_1\subseteq BL_2 \tag{1}
\forall A,B\subseteq \Sigma^*\quad AL_1\subseteq B L_2 \implies A\subseteq B \tag{2}
(A) None of them
(B) Only (1)
(C) Only (2)
(D) Both (1) and (2)
Q: ¿How many of the following equalities are true for every L?
\begin{align*}
L^*&=L^+ \cup \{\lambda\}
\\
L^+&=L^*\setminus \{\lambda\}
\\
\{\lambda\}&=L^*\setminus L^+
\end{align*}
(A) Zero.
(B) One.
(C) Two.
(D) Three.
PS 0 – Exercise 2 (Concatenation — basic properties) \to parts e), f), g)
PS 0 – Exercise 3 (Kleene star — basic properties) \to parts a), c), d), e), f)
PS 0 – Exercise 5 (Reverse — basic properties) \to parts a), b), f)
PS 0 – Exercise 8 (On the size of languages) \to all parts
X,Y sets
A relation f\subseteq X\times Y is a function (and it is denoted as f : X \to Y) if for all x\in X, y,y'\in Y
(x,y)\in f \land (x,y')\in f \implies y=y'
Usually we write f(x)=y. A function is total if for all x\in X exists y\in Y s.t. f(x)=y.
A\subseteq X
f(A) \stackrel{def}{=}\{f(x) \mid x\in A\}
=\{y\in Y \mid \exists x\in A, f(x)=y\}
B\subseteq Y
f^{-1}(B) \stackrel{def}{=}\{ x\in X \mid f(x)\in B\}
Which of the following are true for all A,B?
A function \sigma : \Sigma_1^* \to \Sigma_2^* is a homomorphism if for all w,w'\in \Sigma_1^*,
\sigma(w\cdot w')=\sigma(w)\cdot \sigma(w')
\sigma(\lambda)= ?
When \sigma is a homomorphism, \sigma^{-1} is called inverse homomorphism, but this is a terrible name. Do you see why?
PS0 – Exercise 6 (Homomorphisms I – basic properties) \to all parts
Exercise
L=\{a^nb^mc^\ell \mid n=\ell \lor m=\ell\}
\sigma is the homomorphism given by
\sigma(a)=a
\sigma(b)=b
\sigma(c)=\lambda
\sigma(L)= ?
\mathbf{REGULAR} = the smallest set of languages containing \emptyset, \{\lambda\}, \{s\} for every s\in \Sigma and closed under union, concatenation and Kleene star.
What does it mean that a set is closed under some operation?
A regular expression (regex) is an algebraic expression which tells us how a given language L\in \mathbf{REGULAR} can be constructed from \emptyset, \{\lambda\}, \{s\} for every s\in \Sigma with a finite number of unions, concatenations and Kleene star.
Union is represented with a +, and concatenation \cdot is usually omitted
Example
r=(a+b)^*a(b+bb) represents the language \mathcal{L}(r)=(\{a\}\cup \{b\})^*\cdot \{a\}\cdot(\{b\}\cup \{b\}\cdot\{b\})
This is the language of all words using only as and bs that end with ab or abb.
Data Validation
e.g. ensuring user input matches required formats (e.g. passwords, zip codes, or email addresses)
Data Cleaning and Preprocessing
e.g. cleaning raw data by removing HTML tags, whitespace, or special characters
Text Mining and Extraction
e.g. extracting specific information like dates, URLs …
Log File Analysis and Search
e.g. searching for specific error codes or patterns (e.g., finding all 404 errors or IP addresses)
Search and Replace / Rename in bulk files
Lexical Analysis in Compilers
e.g. programming language compilers use regex to identify keywords, tokens, and operators.
Doubts/questions?
Theorem 1 The language L is regular if one of the following conditions hold:
(1) There is a regular expression r s.t. L=\mathcal{L}(r)
(2) There is a DFA A which accepts exactly the words in L
(3) There is a \lambda-NFA A which accepts exactly the words in L
Proof scheme:
(1)\implies (2): DFAs are closed under union, concatenation and Kleene star.
(2) \implies (1): Arden’s Lemma
(2)\implies (3): trivial
(3)\implies (2): powerset construction aka determinization
Theorem 2 The set of languages \mathbf{REGULAR} is closed under
Can a set be closed under union and complement but not intersection?
Theorem 3 If L is \mathbf{REGULAR} the DFA recognizing L with the smallest number of states is unique (up to renaming of the vertices).
Theorem 4 If L is \mathbf{REGULAR} there is an algorithm to compute the minimum DFA recognizing L.
in a couple of classes
Homework 1
Presentations: Februray 24, March 3, March 10.
Warning
For some exercises we revise part of the theory the class before you’ll present your solution.
It’s way better to have a partially wrong solution than a “chatGPT” solution.