Prima di introdurre le espressioni regoalri (un formalismo per definire linguaggi regolari), è necessario definire alcune operazioni sui linguaggi, che serviranno per dare poi il significato a tali espressioni.
Dati due linguaggi, $L_1$, $L_2$, la loro unione $L_1 \cup L_2$ è l’unione insiemistica dei due linguaggi:
$$ L_1\cup L_2 = \{w \ |\ w \in L_1 \ o \ w \in L_2\} $$
I linguaggi $L_1$ e $L_2$ possono essere definiti su alfabeti diversi: $L_1\subseteq \Sigma^_1$ e $L_2\subseteq \Sigma^_2$. In tal caso, l’unione dei linguaggi è definita sull’unione insiemistica dei due alfabeti: $L_1 \cup L_2 \subseteq (\Sigma_1\cup \Sigma_2)^$. Ad esempio, dati i linguaggi $L_1 = \{0\}^$ e $L_2=\{1\}^*$, la loro unione è:
$$ L_1\cup L_2=\{w\in \{0, 1\}^* \ |\ w=0...0\ o \ w=1...1\} $$
Dati due linguaggi $L_1, L_2$, la loro concatenazione, indicata con $L_1*L_2$ o semplicemente $L_1L_2$, è il linguaggio che contiene tutte le stringhe ottenute concatenando una stringa di $L_1$ con una stringa di $L_2$:
$$ L_1L_2=\{wv \ | \ w \in L_1 \ e \ v \in L_2\} $$
Ad esempio, se $L_1=\{001, 10, 11\}$ e $L_2=\{\epsilon, 001\}$, la concatenazione di questi due linguaggi è:
$$ L_1L_2=\{001\epsilon, 10\epsilon, 11\epsilon, 001001, 10001, 11001\}\\ =\{001, 10, 11, 001001, 10001, 11001\} $$
Considerando invece $L_1=\{0\}^$ e $L_2=\{1\}^$, si ha che:
$$ L_1L_2 = \{w\in \{0, 1\}^*\ |\ w = \underbrace{0...0}_n \underbrace{1...1}_m, n \geq 0, m\geq 0\} $$
Dato un linguaggio $L$, la potenza $i$-esima di $L$ (dove $i$ è un numero intero maggiore o uguale a 0), indicata con $L^i$, è definita induttivamente su $i$:
$$ L^i=\begin{cases} \{\epsilon\} &\text{se }i = 0 \\ L^{i-1}L &\text{se }i> 0 \end{cases} $$
Considerando ad esempio $L=\{0, 11\}$, alcune sue potenze sono: