Замкнутость регулярных языков относительно различных операций

Основные операции

Пусть [math]L_1, L_2[/math] - регулярные языки над одним алфавитом [math]\Sigma[/math]. Тогда следующие языки также являются регулярными:

1. [math]L_1 \cup L_2[/math]
2. [math]L_1 L_2[/math]
3. [math]L_1^*[/math]
4. [math]\overline{L_1}[/math]
5. [math]L_1 \cap L_2[/math]
6. [math]L_1 \setminus L_2[/math]

Доказательство

Свойства 1,2,3 непосредственно следуют из определения регулярных языков.

---

При доказательстве дальнейших свойств воспользуемся эквивалентностью регулярных и автоматных языков. Пусть языки [math]L_1, L_2[/math] распознаются автоматами [math]A_1 = \langle \Sigma , Q_1 , s_1 , T_1 , \delta_1 : Q_1 \times \Sigma \rightarrow 2^{Q_1} \rangle [/math] и [math]A_2 = \langle \Sigma , Q_2 , s_2 , T_2 , \delta_2 : Q_2 \times \Sigma \rightarrow 2^{Q_2} \rangle [/math] соответственно.

---

4. Инвертируем множество допускающих состояний: рассмотрим автомат [math]A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 : Q_1 \times \Sigma \rightarrow 2^{Q_1} \rangle [/math]. Очевидно, он допускает те и только те слова, которые не допускает автомат [math]A_1[/math].

При таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.

---

5. Следует из пунктов 1 и 4, т.к. [math]L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}[/math].

Автомат для пересечения языков можно построить явно, используя конструкцию пересечения автоматов:

[math]A = \langle \Sigma , Q , s , T , \delta : Q \times \Sigma \rightarrow 2^{Q} \rangle [/math], где

[math]Q = \lbrace \langle q_1, q_2 \rangle | q_1 \in Q_1, q_2 \in Q_2 \rbrace[/math]

[math]s = \langle s_1, s_2 \rangle[/math]

[math]T = \lbrace \langle t_1, t_2 \rangle | t_1 \in T_1, t_2 \in T_2 \rbrace[/math]

[math]\delta (\langle q_1,q_2 \rangle, c) = \langle \delta_1 (q_1),\delta_2 (q_2) \rangle[/math]

---

6. [math]L_1 \setminus L_2 = L_1 \cap \overline{L_2}[/math].

Соответствующий автомат строится как произведение автоматов для языков [math]L_1[/math] и [math]\overline {L_2}[/math]