A classe das linguagens regulares é fechada para a operação de união, concatenação e estrela.

Demonstração para União:

Sejam $L_1$ e $L_2$ linguagens regulares. Então existem $N_1=(Q_1,\Sigma_1, \delta_1, q_1, F_1)$ e $N_2=(Q_2,\Sigma_2, \delta_2, q_2, F_2)$ que aceitam $L_1$ e $L_2$, respectivamente. Queremos construir o AFN $N_3$ que aceita a linguagem $L_3=L_1+L_2$.

$Q_3 = Q_1 \cup Q_2 \cup {q_3}$

$\Sigma_3 = \Sigma_1 \cup \Sigma_2$

$F_3=F_1 \cup F_2$

$\delta_3(q,a) = \begin{cases} \text{se } q=q+3\text{ e }a= \varepsilon,\text{ } \delta_3(q,a)={q_1,q_2} \ \text{se } q\in Q_1,\text{ } \delta_3(q,a)=\delta_1(q,a) \ \text{se } q\in Q_2,\text{ } \delta_3(q,a)=\delta_2(q,a) \ \end{cases}$

Demonstração para Concatenação:

Sejam $L_1$ e $L_2$ linguagens regulares. Então existem $N_1=(Q_1,\Sigma_1, \delta_1, q_1, F_1)$ e $N_2=(Q_2,\Sigma_2, \delta_2, q_2, F_2)$ que aceitam $L_1$ e $L_2$, respectivamente. Queremos construir o AFN $N_3$ que aceita a linguagem $L_3=L_1+L_2$.

$Q_3 = Q_1 \cup Q_2$

$\Sigma_3 = \Sigma_1 \cup \Sigma_2$

$F_3=F_2$

$\delta_3(q,a) = \begin{cases} \text{se } q\in F_1 \text{ e } a=\varepsilon, \delta_3(q,a)={q_2} \ \text{se } q\in Q_1, \delta_3(q,a)=\delta_1(q,a) \ \text{se } q\in Q_2, \delta_3(q,a)=\delta_2(q,a) \end{cases}$