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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Прямой и обратный гомоморфизм)
м (-- -> —)
Строка 1: Строка 1:
 
В отличие от [[Замкнутость регулярных языков относительно различных операций|регулярных языков]], [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-языки]] не замкнуты относительно всех теоретико-множественных операций. К примеру, дополнение и пересечение КС-языков не обязательно являются КС-языками.
 
В отличие от [[Замкнутость регулярных языков относительно различных операций|регулярных языков]], [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-языки]] не замкнуты относительно всех теоретико-множественных операций. К примеру, дополнение и пересечение КС-языков не обязательно являются КС-языками.
  
Здесь и далее считаем, что <tex> L_1 </tex> и <tex> L_2 </tex> -- КС языки.
+
Здесь и далее считаем, что <tex> L_1 </tex> и <tex> L_2 </tex> КС языки.
  
 
== Операции с КС-языками ==
 
== Операции с КС-языками ==
Строка 15: Строка 15:
 
Покажем, что <tex> S' \Rightarrow^{*} w \iff S \Rightarrow^{*} w \lor T \Rightarrow^{*} w </tex>. В левую сторону: поскольку <tex> S \Rightarrow^{*} w </tex> и есть правило <tex> S' \to S </tex>, то, по определению <tex> \Rightarrow^{*} </tex> получаем, что <tex> S' \Rightarrow^{*} w </tex>. Аналогично и для <tex> T </tex>.
 
Покажем, что <tex> S' \Rightarrow^{*} w \iff S \Rightarrow^{*} w \lor T \Rightarrow^{*} w </tex>. В левую сторону: поскольку <tex> S \Rightarrow^{*} w </tex> и есть правило <tex> S' \to S </tex>, то, по определению <tex> \Rightarrow^{*} </tex> получаем, что <tex> S' \Rightarrow^{*} w </tex>. Аналогично и для <tex> T </tex>.
  
В обратную сторону, пусть <tex> S' \Rightarrow^{*} w </tex>. Поскольку <tex> S' \to S\,|\,T </tex> -- единственные правила, в которых нетерминал <tex> S' </tex> присутствует в правой части, а значит, либо <tex> S' \Rightarrow S \Rightarrow^{*} w </tex>, либо <tex> S' \Rightarrow T \Rightarrow^{*} w </tex>, что и требовалось доказать.
+
В обратную сторону, пусть <tex> S' \Rightarrow^{*} w </tex>. Поскольку <tex> S' \to S\,|\,T </tex> единственные правила, в которых нетерминал <tex> S' </tex> присутствует в правой части, а значит, либо <tex> S' \Rightarrow S \Rightarrow^{*} w </tex>, либо <tex> S' \Rightarrow T \Rightarrow^{*} w </tex>, что и требовалось доказать.
  
 
}}
 
}}
Строка 22: Строка 22:
  
 
{{ Утверждение
 
{{ Утверждение
|statement=  <tex> L_1 \cdot L_2 </tex> -- КС-язык.
+
|statement=  <tex> L_1 \cdot L_2 </tex> КС-язык.
|proof=КС-грамматика для <tex> L_1 \cdot L_2 </tex> выглядит следующим образом: <tex> S' \to S T </tex>, и <tex> S </tex> -- стартовый символ.
+
|proof=КС-грамматика для <tex> L_1 \cdot L_2 </tex> выглядит следующим образом: <tex> S' \to S T </tex>, и <tex> S </tex> стартовый символ.
 
Доказательство аналогично случаю с объединением.
 
Доказательство аналогично случаю с объединением.
 
}}
 
}}
Строка 30: Строка 30:
  
 
{{ Утверждение
 
{{ Утверждение
|statement=  <tex> L^{*} = \bigcup\limits_{i = 0}^{\infty} L^i </tex> -- КС-язык.
+
|statement=  <tex> L^{*} = \bigcup\limits_{i = 0}^{\infty} L^i </tex> КС-язык.
|proof=Если <tex> S </tex> -- стартовый символ КС-грамматики для языка <tex> L </tex>, то добавим в КС-грамматику для языка <tex> L^{*} </tex> новый стартовый символ <tex> S' </tex> и правила <tex> S' \to S S' \, | \, \varepsilon </tex>.  
+
|proof=Если <tex> S </tex> стартовый символ КС-грамматики для языка <tex> L </tex>, то добавим в КС-грамматику для языка <tex> L^{*} </tex> новый стартовый символ <tex> S' </tex> и правила <tex> S' \to S S' \, | \, \varepsilon </tex>.  
 
}}
 
}}
  
Строка 55: Строка 55:
  
 
{{ Утверждение
 
{{ Утверждение
|statement= <tex> L = \{ww \mid w \in \Sigma^{*} \} </tex> не является КС-языком, однако <tex> \overline{L} </tex> -- КС-язык.
+
|statement= <tex> L = \{ww \mid w \in \Sigma^{*} \} </tex> не является КС-языком, однако <tex> \overline{L} </tex> КС-язык.
 
|proof=
 
|proof=
  
То, что <tex> L </tex> -- не КС язык, доказывается с помощью леммы о разрастании. Для <tex> \overline{L} </tex> можно составить [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]].
+
То, что <tex> L </tex> не КС язык, доказывается с помощью леммы о разрастании. Для <tex> \overline{L} </tex> можно составить [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]].
 
}}
 
}}
  
Строка 80: Строка 80:
 
}}
 
}}
  
Операция <tex> Half </tex> также не сохраняет КС-язык таковым. Рассмотрим язык <tex> L = \{ a^n b a^n b a^m b a^l b a^k b a^k b \} </tex>. <tex> L </tex> -- КС-язык. Посмотрим, что есть <tex> Half(L) </tex>. Пусть <tex> \alpha = a^n b a^n b a^m b a^l b a^k b a^k b = ww </tex>. Отсюда следует, что:
+
Операция <tex> Half </tex> также не сохраняет КС-язык таковым. Рассмотрим язык <tex> L = \{ a^n b a^n b a^m b a^l b a^k b a^k b \} </tex>. <tex> L </tex> КС-язык. Посмотрим, что есть <tex> Half(L) </tex>. Пусть <tex> \alpha = a^n b a^n b a^m b a^l b a^k b a^k b = ww </tex>. Отсюда следует, что:
 
* <tex> n = l </tex>
 
* <tex> n = l </tex>
 
* <tex> n = k </tex>
 
* <tex> n = k </tex>
Строка 91: Строка 91:
 
=== Пересечение ===
 
=== Пересечение ===
  
Тем не менее, хоть пересечение двух КС-языков не обязательно является КС-языком, но пересечение КС-языка и регулярного языка -- всегда КС-язык. Для доказательства этого построим МП-автомат для пересечения регулярного языка и КС-языка.
+
Тем не менее, хоть пересечение двух КС-языков не обязательно является КС-языком, но пересечение КС-языка и регулярного языка всегда КС-язык. Для доказательства этого построим МП-автомат для пересечения регулярного языка и КС-языка.
  
Пусть регулярный язык задан своим [[Детерминированные конечные автоматы|ДКА]], а КС-язык -- своим МП-автоматом c допуском по допускающему состоянию. Построим прямое произведение этих автоматов так же, как строилось прямое произведение для двух ДКА.
+
Пусть регулярный язык задан своим [[Детерминированные конечные автоматы|ДКА]], а КС-язык своим МП-автоматом c допуском по допускающему состоянию. Построим прямое произведение этих автоматов так же, как строилось прямое произведение для двух ДКА.
  
Более формально, пусть <tex> R </tex> -- регулярный язык, заданный своим ДКА <tex> \langle \Sigma, Q_1, s_1, T_1, \delta_1 \rangle </tex>, и <tex> L </tex> -- КС-язык, заданный своим МП-автоматом: <tex> \langle \Sigma, \Gamma, Q_2, s_2, T_2, z_0, \delta_2 \rangle </tex>. Тогда прямым произведением назовем следующий автомат:
+
Более формально, пусть <tex> R </tex> регулярный язык, заданный своим ДКА <tex> \langle \Sigma, Q_1, s_1, T_1, \delta_1 \rangle </tex>, и <tex> L </tex> КС-язык, заданный своим МП-автоматом: <tex> \langle \Sigma, \Gamma, Q_2, s_2, T_2, z_0, \delta_2 \rangle </tex>. Тогда прямым произведением назовем следующий автомат:
  
* <tex> Q = \{ \langle q_1, q_2 \rangle \mid q_1 \in Q_1, q_2 \in Q_2 \} </tex>. Иначе говоря, состояние в новом автомате -- пара из состояния первого автомата и состояния второго автомата.
+
* <tex> Q = \{ \langle q_1, q_2 \rangle \mid q_1 \in Q_1, q_2 \in Q_2 \} </tex>. Иначе говоря, состояние в новом автомате пара из состояния первого автомата и состояния второго автомата.
 
* <tex> s = \langle s_1, s_2 \rangle </tex>
 
* <tex> s = \langle s_1, s_2 \rangle </tex>
 
* Стековый алфавит <tex> \Gamma </tex> остается неизменным.
 
* Стековый алфавит <tex> \Gamma </tex> остается неизменным.
* <tex> T = \{ \langle t_1, t_2 \rangle \mid t_1 \in T_1, t_2 \in T_2 \} </tex>. Допускающие состояния нового автомата -- пары состояний, где оба состояния были допускающими в своем автомате.
+
* <tex> T = \{ \langle t_1, t_2 \rangle \mid t_1 \in T_1, t_2 \in T_2 \} </tex>. Допускающие состояния нового автомата пары состояний, где оба состояния были допускающими в своем автомате.
 
* <tex> \delta ( \langle q_1, q_2 \rangle, c, d) = \langle \delta_1 (q_1, c), \delta_2 (q_2, c, d) \rangle </tex>. При этом на стек кладется то, что положил бы изначальный МП-автомат при совершении перехода из состояния <tex> q_2 </tex>,  
 
* <tex> \delta ( \langle q_1, q_2 \rangle, c, d) = \langle \delta_1 (q_1, c), \delta_2 (q_2, c, d) \rangle </tex>. При этом на стек кладется то, что положил бы изначальный МП-автомат при совершении перехода из состояния <tex> q_2 </tex>,  
 
видя на ленте символ <tex> c </tex> и символ <tex> d </tex> на вершине стека.
 
видя на ленте символ <tex> c </tex> и символ <tex> d </tex> на вершине стека.

Версия 21:13, 21 октября 2013

В отличие от регулярных языков, КС-языки не замкнуты относительно всех теоретико-множественных операций. К примеру, дополнение и пересечение КС-языков не обязательно являются КС-языками.

Здесь и далее считаем, что [math] L_1 [/math] и [math] L_2 [/math] — КС языки.

Операции с КС-языками

Объединение

Утверждение:
[math] L_1 \cup L_2 [/math] также является КС-языком.
[math]\triangleright[/math]

Построим КС-грамматику для языка [math] L_1 \cup L_2 [/math]. Для этого рассмотрим соответствующие КС-грамматики для языков [math] L_1 [/math] и [math] L_2 [/math]. Пусть стартовые символы в них имеют имена [math] S [/math] и [math] T [/math] соответственно. Тогда стартовый символ для [math] L_1 \cup L_2 [/math] обозначим за [math] S' [/math] и добавим правило [math] S' \to S\,|\,T [/math].

Покажем, что [math] S' \Rightarrow^{*} w \iff S \Rightarrow^{*} w \lor T \Rightarrow^{*} w [/math]. В левую сторону: поскольку [math] S \Rightarrow^{*} w [/math] и есть правило [math] S' \to S [/math], то, по определению [math] \Rightarrow^{*} [/math] получаем, что [math] S' \Rightarrow^{*} w [/math]. Аналогично и для [math] T [/math].

В обратную сторону, пусть [math] S' \Rightarrow^{*} w [/math]. Поскольку [math] S' \to S\,|\,T [/math] — единственные правила, в которых нетерминал [math] S' [/math] присутствует в правой части, а значит, либо [math] S' \Rightarrow S \Rightarrow^{*} w [/math], либо [math] S' \Rightarrow T \Rightarrow^{*} w [/math], что и требовалось доказать.
[math]\triangleleft[/math]

Конкатенация

Утверждение:
[math] L_1 \cdot L_2 [/math] — КС-язык.
[math]\triangleright[/math]

КС-грамматика для [math] L_1 \cdot L_2 [/math] выглядит следующим образом: [math] S' \to S T [/math], и [math] S [/math] — стартовый символ.

Доказательство аналогично случаю с объединением.
[math]\triangleleft[/math]

Замыкание Клини

Утверждение:
[math] L^{*} = \bigcup\limits_{i = 0}^{\infty} L^i [/math] — КС-язык.
[math]\triangleright[/math]
Если [math] S [/math] — стартовый символ КС-грамматики для языка [math] L [/math], то добавим в КС-грамматику для языка [math] L^{*} [/math] новый стартовый символ [math] S' [/math] и правила [math] S' \to S S' \, | \, \varepsilon [/math].
[math]\triangleleft[/math]

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

В случае с прямым гомоморфизмом всё просто: строится КС-грамматика, в которой каждый символ [math] x \in \Sigma [/math] заменяется на [math] h(x) [/math]. Для обратного гомоморфизма можно построить МП-автомат для [math] h^{-1}(L) [/math] на основе МП-автомата для языка [math] L [/math] (назовем его [math] M [/math]). Считаем, что [math] M [/math] допускает слова по пустому стеку. Новый автомат будет действовать следующим образом:

  1. Если входное слово закончилось, допускаем либо не допускаем его по пустому стеку.
  2. Иначе считываем символ [math] x [/math].
  3. Сохраняем [math] h(x) [/math] в буффере.
  4. Запускаем [math] M [/math] на слове, находящемся в буфере.
  5. После того, как [math] M [/math] обработал весь буфер, переходим к пункту 2.

Пусть в автомате [math] M [/math] было [math] n [/math] состояний. Для того, чтобы научиться сохранять слова в буфере, создадим [math] |\Sigma|^{k+1} n [/math] дополнительных состояний в новом автомате, где [math] k = \max\limits_{c \in \Sigma} | h(c) | [/math]. Это позволит в состоянии кодировать слово, которое находится сейчас в буфере. Переходы в этих состояниях совершаются на основе того, что стоит на первом месте в буфере, состояния автомата и вершины стека. На ленту переходы в этих состояниях не смотрят. Из состояния, в котором буфер пуст, добавим [math] \varepsilon [/math]-переход в начальное состояние. Необходима картинка.

Разворот

Для того, чтобы построить КС-грамматику для языка [math] L^{R} = \{ w^{R} \mid w \in L \} [/math], необходимо развернуть все правые части правил грамматики для [math] L [/math].

Дополнение, пересечение и разность

В отличие от регулярных языков, дополнение до КС-языка, пересечение КС-языков и разность КС-языков может не быть КС-языком.

Утверждение:
[math] L = \{ww \mid w \in \Sigma^{*} \} [/math] не является КС-языком, однако [math] \overline{L} [/math] — КС-язык.
[math]\triangleright[/math]
То, что [math] L [/math] — не КС язык, доказывается с помощью леммы о разрастании. Для [math] \overline{L} [/math] можно составить КС-грамматику.
[math]\triangleleft[/math]
Утверждение:
Если [math] L_1 = a^i b^i c^j , L_2 = a^i b^j c^j [/math], то [math] L_1 \cap L_2 [/math] не является КС-языком.
[math]\triangleright[/math]

[math] L_1 = \{ a^i b^i \} \cdot \{ c^j \}, L_2 = \{ a^i \} \cdot \{ b^j c^j \} [/math]. По замкнутости КС-языков относительно конкатенации получаем, что [math] L_1 [/math] и [math] L_2 [/math] являются КС-языками.

Но [math] L_1 \cap L_2 = \{ a^i b^i c^i \mid i \in \mathbb{N} \} [/math], что по лемме о разрастании для КС-языков не является КС-языком.
[math]\triangleleft[/math]

Для разности достаточно заметить, что [math] \overline{L} = \Sigma^{*} \setminus L [/math], поэтому разность КС-языков также необязательно является КС-языком.

Более того, задачи определения того, является ли дополнение КС-языка КС-языком и проверки непустоты пересечения КС-языков являются алгоритмически неразрешимыми.

Примеры других операций

Определение:
[math] Half(L) = \{ w \mid ww \in L \} [/math]


Операция [math] Half [/math] также не сохраняет КС-язык таковым. Рассмотрим язык [math] L = \{ a^n b a^n b a^m b a^l b a^k b a^k b \} [/math]. [math] L [/math] — КС-язык. Посмотрим, что есть [math] Half(L) [/math]. Пусть [math] \alpha = a^n b a^n b a^m b a^l b a^k b a^k b = ww [/math]. Отсюда следует, что:

  • [math] n = l [/math]
  • [math] n = k [/math]
  • [math] m = k [/math]

А значит, [math] n = l = k = m [/math], и [math] Half(L) = \{ a^n b a^n b a^n b \} [/math], и по лемме о разрастании КС-языком не является.

Операции над КС-языком и регулярным языком

Пересечение

Тем не менее, хоть пересечение двух КС-языков не обязательно является КС-языком, но пересечение КС-языка и регулярного языка — всегда КС-язык. Для доказательства этого построим МП-автомат для пересечения регулярного языка и КС-языка.

Пусть регулярный язык задан своим ДКА, а КС-язык — своим МП-автоматом c допуском по допускающему состоянию. Построим прямое произведение этих автоматов так же, как строилось прямое произведение для двух ДКА.

Более формально, пусть [math] R [/math] — регулярный язык, заданный своим ДКА [math] \langle \Sigma, Q_1, s_1, T_1, \delta_1 \rangle [/math], и [math] L [/math] — КС-язык, заданный своим МП-автоматом: [math] \langle \Sigma, \Gamma, Q_2, s_2, T_2, z_0, \delta_2 \rangle [/math]. Тогда прямым произведением назовем следующий автомат:

  • [math] Q = \{ \langle q_1, q_2 \rangle \mid q_1 \in Q_1, q_2 \in Q_2 \} [/math]. Иначе говоря, состояние в новом автомате — пара из состояния первого автомата и состояния второго автомата.
  • [math] s = \langle s_1, s_2 \rangle [/math]
  • Стековый алфавит [math] \Gamma [/math] остается неизменным.
  • [math] T = \{ \langle t_1, t_2 \rangle \mid t_1 \in T_1, t_2 \in T_2 \} [/math]. Допускающие состояния нового автомата — пары состояний, где оба состояния были допускающими в своем автомате.
  • [math] \delta ( \langle q_1, q_2 \rangle, c, d) = \langle \delta_1 (q_1, c), \delta_2 (q_2, c, d) \rangle [/math]. При этом на стек кладется то, что положил бы изначальный МП-автомат при совершении перехода из состояния [math] q_2 [/math],

видя на ленте символ [math] c [/math] и символ [math] d [/math] на вершине стека.

Этот автомат использует в качестве состояний пары из двух состояний каждого автомата, а за операции со стеком отвечает только МП-автомат. Слово допускается этим автоматом [math] \iff [/math] слово допускается и ДКА и МП-автоматом, то есть язык данного автомата совпадает с [math] R \cap L [/math].

Разность

Разность КС-языка и регулярного языка выражается следующим образом: [math] L \setminus R = L \cap \overline{R} [/math], а, поскольку регулярные языки замкнуты относительно дополнения, то разность можно выразить через пересечение.