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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Основные операции== Пусть <tex>L_1, L_2</tex> - регулярные языки над одним алфавитом <tex>\Sigma</tex>. Тог…»)
 
(Доказательство)
Строка 8: Строка 8:
 
#<tex>L_1 \setminus L_2</tex>
 
#<tex>L_1 \setminus L_2</tex>
 
===Доказательство===
 
===Доказательство===
Свойства 1,2,3 непосредственно следуют из определения регулярных языков
+
Свойства 1,2,3 непосредственно следуют из определения регулярных языков.
 +
 
 
При доказательстве дальнейших свойств воспользуемся эквивалентностью регулярных и автоматных языков. Пусть языки <tex>L_1, L_2</tex> распознаются автоматами <tex>A_1 = \langle \Sigma , Q_1 , s_1 , T_1 , \delta_1 : Q_1 \times \Sigma \rightarrow 2^{Q_1} \rangle </tex> и <tex>A_2 = \langle \Sigma , Q_2 , s_2 , T_2 , \delta_2 : Q_2 \times \Sigma \rightarrow 2^{Q_2} \rangle </tex> соответственно.
 
При доказательстве дальнейших свойств воспользуемся эквивалентностью регулярных и автоматных языков. Пусть языки <tex>L_1, L_2</tex> распознаются автоматами <tex>A_1 = \langle \Sigma , Q_1 , s_1 , T_1 , \delta_1 : Q_1 \times \Sigma \rightarrow 2^{Q_1} \rangle </tex> и <tex>A_2 = \langle \Sigma , Q_2 , s_2 , T_2 , \delta_2 : Q_2 \times \Sigma \rightarrow 2^{Q_2} \rangle </tex> соответственно.
  

Версия 23:44, 7 октября 2010

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

Пусть [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.