Theory of computation

2025-2026 Q2

Ilario Bonacina
ilario.bonacina@upc.edu

Universitat Politècnica de Catalunya

February 17, 2026

This class

  • homomorphisms
  • more exercises from PS 0
  • a “study guide” on \mathbf{REGULAR} languages

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

A mathematical interlude

Functions

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?

  • f(f^{-1}(B))=B
  • f(f^{-1}(B))\subseteq B
  • f^{-1}(f(A)) = A
  • f^{-1}(f(A))\supseteq A

Homomorphisms

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)= ?

Homomorphism are easy to describe
just say what is \sigma(s) for each s\in \Sigma_1^*
why this is enough?

When \sigma is a homomorphism, \sigma^{-1} is called inverse homomorphism, but this is a terrible name. Do you see why?

Exercises

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)= ?

PS0 – Exercise 7 (Homomorphisms II – basic properties) @ home

Back to formal languages

\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?

Regular expressions

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.

Regex in the “real” world

  • 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.

Last lab – DFAs

Doubts/questions?

REGULAR – equivalent descriptions

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

REGULAR – closure properties

Theorem 2 The set of languages \mathbf{REGULAR} is closed under

  • union
  • complement
  • intersection
  • reverse
  • concatenation
  • Kleene star
  • homomorphism
  • inverse homomorphism

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.

How to show that a language L is not regular?

  • Pumping Lemma
  • distinguishing extensions

in a couple of classes

Upcoming classes

Tomorrow
more theory on DFAs/\lambda-NFAs, exercises on RACSO
Next Tuesday
  • proof techniques
  • minimization algorithm (Moore)
  • exercises on Regular languages (Homework 1)

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.

  • What you’ll send to the “Practiques” could be projected as supporting material for your presentation.
    • Keep it short (1-2 pages at most. Not a lot of text…)
    • Each presentation lasts < 10 minutes.