Teorema: Siano $L_1$ e $L_2$ linguaggi regolari. Allora, $L_1 \cup L_2$ è un linguaggio regolare.
Questa proprietà, così come le altre proprietà di questo tipo, può essere dimostrata usando uno qualunque dei formalismi che caratterizzano la classe dei linguaggi regolari: i DFA, gli NFA, gli $\epsilon$-NFA o le espressioni regolari. In questo caso, il formalismo più comodo è quello delle espressioni regolari.
Siccome $L_1$ è regolare, esiste un’espressione regolare $E_1$ tale che $L(E_1)=L_1$. Analogamente, poichè $L_2$ è regolare, esiste un’espressione regolare $E_2$ tale che $L(E_2)=L_2$. Si può quindi costruire l’espressione regolare $E_1 + E_2$, che per la semantica dell’operatore $+$ genera il linguaggio regolare
$$ L(E_1 + E_2)=L(E_1)\cup L(E_2)=L_1\cup L_2 $$
ovvero $L_1\cup L_2$ è un linguaggio regolare.
Dato un linguaggio $L\subseteq \Sigma^$, il complemento di $L$ è il linguaggio $\overline L = \Sigma^\setminus L$.
Teorema: Se $L$ è un linguaggio regolare, allora $\overline L$ è un linguaggio regolare.
Questa volta, la dimostrazione viene fatta utilizzando la caratterizzazione dei linguaggi reglari tramite i DFA. Per definizione, se $L$ è regolare esiste un DFA $A=\lang Q, \Sigma, \delta, q_0, F\rang$ tale che $L(A)=L$. Si costriusce poi un altro automa $\overline A = \lang Q, \Sigma, \delta, q_0, Q\setminus F\rang$, che ha tutti gli stessi elementi di $A$, ad eccezione l’insieme degli stati finali, che in $\overline A$ contiene tutti e soli gli stati non finali di $A$.
Data una stringa $w\in L$, si deduce che
cioè che una stringa appartiene a $L$ se e solo se non appartiene a $L(\overline A)$: questo vuol dire che $L(\overline A)=\overline L$. Così, si conclude che $\overline L$ è un linguaggio regolare, in quanto riconosciuto da un DFA.
Le proprietà dei linguaggi regolari appena viste, così come quelle che verranno presentate successivamente, forniscono ulteriori strumenti per dimostrare che un linguaggio non è regolare.
Ad esempio, il linguaggio
$$ L_{eq}=\{w \in \{0, 1\}^* \ | \ w \text{ contiene lo stesso numero di } 0 \ e \ 1\} $$
non è regolare, e lo si può dimostrare con la tecnica basata sul pumping lemma, ragionando sulla stringa $0^m1^m$, dove $m\geq N$ e $N$ è la costante di pumping (supponendo per assurdo che $L_{eq}$ sia regolare). Il ragionamento è uguale a quello svolto nella dimostrazione del fatto che il linguaggio $\{0 ^n 1^n\ | \ n \geq 1\}$ non è regolare.
Si consideri ora il linguaggio