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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
|statement=
 
|statement=
 
Пусть <tex>L_1, L_2</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярные языки]] над одним алфавитом <tex>\Sigma</tex>. Тогда следующие языки также являются регулярными:
 
Пусть <tex>L_1, L_2</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярные языки]] над одним алфавитом <tex>\Sigma</tex>. Тогда следующие языки также являются регулярными:
#Языки, полученные путём применения основных теоретико-множественных операций:
+
#Языки, полученные путём применения следующих теоретико-множественных операций:
 
#*<tex>L_1 \cup L_2</tex>,
 
#*<tex>L_1 \cup L_2</tex>,
 
#*<tex>\overline{L_1}</tex>,
 
#*<tex>\overline{L_1}</tex>,

Версия 07:40, 21 января 2012

Теорема:
Пусть [math]L_1, L_2[/math]регулярные языки над одним алфавитом [math]\Sigma[/math]. Тогда следующие языки также являются регулярными:
  1. Языки, полученные путём применения следующих теоретико-множественных операций:
    • [math]L_1 \cup L_2[/math],
    • [math]\overline{L_1}[/math],
    • [math]L_1 \cap L_2[/math],
    • [math]L_1 \setminus L_2[/math];
  2. [math]L_1^*[/math];
  3. [math]L_1 L_2[/math];
  4. [math]\overset{\leftarrow}{L_1}[/math].
Доказательство:
[math]\triangleright[/math]

Как известно, классы регулярных и автоматных языков совпадают. Пусть языки [math]L_1[/math] и [math]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] соответственно.

    • [math]L_1 \cup L_2[/math] является регулярным по определению регулярных языков.
    • Рассмотрим автомат [math]A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 \rangle [/math], то есть автомат [math]A[/math], в котором терминальные и нетерминальные состояния инвертированы (при таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.) Очевидно, он допускает те и только те слова, которые не допускает автомат [math]A_1[/math], а значит, задаёт язык [math]\overline{L_1}[/math]. Таким образом, [math]\overline{L_1}[/math] — регулярный.
    • [math]L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}[/math]. Тогда [math]L_1 \cap L_2[/math] — регулярный. Также автомат для пересечения языков можно построить явно, используя конструкцию произведения автоматов.
    • [math]L_1 \setminus L_2 = L_1 \cap \overline{L_2}[/math]. Тогда [math]L_1 \setminus L_2[/math] — регулярный.
  1. [math]L_1^*[/math] является регулярным по определению регулярных языков.
  2. [math]L_1 L_2[/math] также является регулярным по определению регулярных языков.
  3. Рассмотрим НКА c [math]\varepsilon[/math]-переходами [math]A_1' = \langle \Sigma, Q_1, s' , \lbrace s_1 \rbrace, \delta_1' \rangle [/math], где [math]\delta_1' (v,c) = \lbrace u | \delta_1(u,c) = v \rbrace [/math]; [math]\delta_1'(s', \varepsilon) = \lbrace T_i \rbrace[/math]. Если в исходном автомате путь по [math]\alpha[/math] из [math]s_1[/math] приводил в терминальное состояние, то в новом автомате существует путь по [math]\alpha[/math] из этого терминального состояния в [math]s_1[/math] (и наоборот). Следовательно, этот автомат распознает в точности развернутые слова языка [math]L_1[/math]. Тогда язык [math]\overset{\leftarrow}{L_1}[/math] — регулярный.
[math]\triangleleft[/math]

Прямой и обратный гомоморфизмы

Определение:
Отображение [math]\varphi : \Sigma_1^* \to \Sigma_2^*[/math], сохраняющее операцию конкатенации [math](\varphi(\alpha\beta) = \varphi(\alpha) \varphi(\beta))[/math], называется гомоморфизмом.

Гомоморфизм однозначно задается значениями на алфавите: [math]\varphi(\overline{c_1 c_2 \ldots c_k}) = \varphi(c_1) \varphi(c_2)\ldots \varphi(c_k)[/math].


Определение:
Образом языка [math]L \subset \Sigma_1^*[/math] при гомоморфизме [math]\varphi: \Sigma_1^* \rightarrow \Sigma_2^*[/math] называется язык [math]\varphi (L) \overset{\underset{\mathrm{def}}{}}{=} \lbrace \varphi (x) | x \in L \rbrace[/math].


Определение:
Прообразом языка [math]L \subset \Sigma_2^*[/math] при гомоморфизме [math]\varphi: \Sigma_1^* \rightarrow \Sigma_2^*[/math] называется язык [math]\varphi^{-1} (L) \overset{\underset{\mathrm{def}}{}}{=} \lbrace x | \varphi (x) \in L \rbrace[/math].


Утверждение:
[math]L \subset \Sigma_1^*[/math] — регулярный , [math]\varphi:\Sigma_1^* \rightarrow \Sigma_2^* [/math] — гомоморфизм. Тогда [math]\varphi(L)[/math] — регулярный.
[math]\triangleright[/math]
Рассмотрим ДКА, распознающий [math]L[/math]. Заменим в нем все переходы по символам на переходы по их образам при гомоморфизме. Полученный автомат (с переходами по строкам) распознает в точности [math]\varphi(L)[/math] и имеет эквивалентный ДКА.
[math]\triangleleft[/math]
Утверждение:
[math]L \subset \Sigma_2^*[/math] — регулярный , [math]\varphi:\Sigma_1^* \rightarrow \Sigma_2^* [/math] — гомоморфизм. Тогда [math]\varphi^{-1}(L)[/math] — регулярный.
[math]\triangleright[/math]
Рассмотрим ДКА, распознающий [math]L[/math]. Отследим для каждого состояния [math]u[/math] и символа [math]c[/math] строку [math]\varphi(c)[/math]: [math] \langle u,\varphi(c) \rangle \vdash^* \langle v,\varepsilon \rangle[/math] и положим [math]\delta (u,c) = v[/math] в новом автомате (на том же множестве состояний). Автомат с построенной таким образом функцией переходов, очевидно, распознает слова языка [math]\varphi^{-1}(L)[/math] и только их.
[math]\triangleleft[/math]