В отличие от регулярных языков, КС-языки не замкнуты относительно всех теоретико-множественных операций. К примеру, дополнение и пересечение КС-языков не обязательно являются КС-языками.
Здесь и далее считаем, что [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]\Rightarrow[/math]
- Поскольку [math] S \Rightarrow^{*} w [/math] и есть правило [math] S' \to S [/math], то, по определению [math] \Rightarrow^{*} [/math] получаем, что [math] S' \Rightarrow^{*} w [/math]. Аналогично и для [math] T [/math].
[math]\Leftarrow [/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 L_2 [/math] — КС-язык. |
| [math]\triangleright[/math] |
|
Аналогично предыдущему случаю построим КС-грамматику для языка [math] L_1 L_2 [/math]. Для этого добавим правило [math] S' \to S T [/math], где [math] S [/math] и [math] T [/math] — стартовые символы языков [math] L_1 [/math] и [math] L_2 [/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]\triangleright[/math] |
|
Построим КС-грамматику, в которой каждый символ [math] x \in \Sigma [/math] заменим на [math] h(x) [/math]. |
| [math]\triangleleft[/math] |
| Утверждение: |
КС-языки замкнуты относительно обратного гомоморфизма. |
| [math]\triangleright[/math] |
|
Для доказательства замкнутости обратного гомоморфизма будем делать аналогично доказательству для регулярных языков. Построим МП-автомат для [math] h^{-1}(L) = \{ w \mid h(w) \in L \} [/math] на основе МП-автомата для языка [math] L [/math] (назовем его [math] M [/math]). Новый автомат [math] M' [/math] будет действовать следующим образом:
- Если входное слово закончилось, допускаем или не допускаем его по допускающему состоянию.
- Считываем символ [math] c [/math].
- Сохраняем [math] h(c) [/math] в буфере (входная лента для автомата [math] M [/math]).
- Запускаем [math] M [/math] на слове, находящемся в буфере.
- После того, как [math] M [/math] обработал весь буфер, переходим к пункту 1.
Если рассмотреть более формально, пусть [math] M =\langle Q, \Sigma, \Gamma, \delta, s, Z_{0}, T\rangle [/math], тогда [math] M' =\langle Q', \Sigma, \Gamma, \delta', (s, \varepsilon), Z_{0}, T \times {\varepsilon}\rangle[/math].
- [math] Q' = \{ (q, x) \mid q \in Q \} [/math], где [math] x [/math] — суффикс (не обязательно собственный) некоторой цепочки [math] h(c) [/math] для символа [math] c \in \Sigma [/math]. Таким образом, первый компонент состояния [math] M' [/math] является состоянием [math] M [/math], а второй — компонентом буфера.
- [math] \delta' [/math] определяется следующими правилами:
- [math] \delta'((q, \varepsilon), c, X) = \{((q, h(c)), X) \mid c \in \Sigma, q \in Q, X \in \Gamma \}[/math]. Когда буфер пуст, [math] M' [/math] может прочитать свой следующий входной символ [math] c [/math] и поместить [math] h(c) [/math] в буфер.
- Если [math] (p, \gamma) \in \delta(q, b, X), b \in T \cup \varepsilon [/math], то [math] ((p, x), \gamma) \in \delta'((q, bx), \varepsilon, X) [/math]. Таким образом, [math] M' [/math] всегда имеет возможность имитации перехода [math] M [/math], используя голову буфера. Если [math] b \in T [/math], то буфер должен быть непустым, но если [math] b = \varepsilon [/math], то буфер может быть пустым.
- Начальным состоянием [math] M' [/math] является [math] (s, \varepsilon) [/math], т.е. [math] M' [/math] стартует в начальном состоянии [math] M [/math] с пустым буфером.
- Допускающими состояниями [math] M' [/math] являются состояния [math] (q, \varepsilon)[/math], где [math] q \in T [/math].
Таким образом получаем, что [math](s, h(w), Z_0) \vdash_M^{*} (p, \varepsilon, \gamma) \Leftrightarrow ((s, \varepsilon), w, Z_0) \vdash_{M'}^{*} ((p, \varepsilon), \varepsilon, \gamma)[/math], то есть автомат [math] M' [/math] допускает те и только те слова, которые принадлежат языку [math] h^{-1}(L) [/math]. |
| [math]\triangleleft[/math] |
Разворот
| Утверждение: |
[math] L^{R} = \{ w^{R} \mid w \in L \}[/math] контекстно-свободна. |
| [math]\triangleright[/math] |
|
Для того, чтобы построить [math] L^{R} [/math], необходимо развернуть все правые части правил грамматики для [math] L [/math].
Покажем, что [math]w \in L \iff w^{R} \in L^{R}[/math]. Докажем ([math]\Rightarrow[/math]) индукцией по длине порождения в грамматике [math]L[/math]. В обратную сторону ([math]\Leftarrow[/math]) рассуждения аналогичны.
База. [math]A \underset{L}{\Rightarrow} w[/math].
В грамматике [math]L[/math] существует правило [math]A \rightarrow w[/math] и, так как мы развернули все правые части правил, то [math]A \underset{L^{R}}{\Rightarrow} w^{R}[/math].
Предположение индукции. Пусть [math]A \underset{L}{\Rightarrow}^* w[/math] менее чем за [math]n[/math] шагов, тогда [math]A \underset{L^{R}}{\Rightarrow}^* w^{R}[/math].
Переход. Пусть в порождении [math]n[/math] шагов, [math]n \gt 1[/math]. Тогда оно имеет вид [math]A \underset{L}{\Rightarrow}Y_1 Y_2...Y_m \underset{L}{\Rightarrow}^*w[/math], где [math] Y_i \in N \cup \Sigma [/math]. Цепочку [math] w [/math] можно разбить на [math]w_1 w_2...w_m[/math], где [math] Y_i \underset{L}{\Rightarrow}^*w_i[/math]. Так как каждое из порождений [math] Y_i \underset{L}{\Rightarrow}^*w_i [/math] содержит менее [math] n [/math] шагов, к ним можно применить предположение индукции и заключить, что [math] Y_i \underset{L^{R}}{\Rightarrow}^*w_i^{R} [/math]. Так как [math]A \underset{L}{\Rightarrow}Y_1 Y_2...Y_m[/math], то [math]A \underset{L^{R}}{\Rightarrow}Y_m Y_{m - 1}...Y_1[/math], откуда следует, что [math] A \underset{L^{R}}{\Rightarrow}^* w^{R} [/math]. |
| [math]\triangleleft[/math] |
Пример разворота:
Пусть задана КС-грамматика [math]G[/math] для языка [math]L = a^i b^j c^i[/math] со следующими правилами:
- [math] A \to bA \mid \varepsilon [/math]
- [math] B \to aBc \mid A [/math]
В таком случае КС-грамматика [math]G^R[/math] для языка [math]L^R = c^i b^j a^i [/math] выглядит следующим образом:
- [math] A \to Ab \mid \varepsilon [/math]
- [math] B \to cBa \mid A [/math]
Дополнение, пересечение и разность
В отличие от регулярных языков, дополнение до КС-языка, пересечение КС-языков и разность КС-языков может не быть КС-языком.
| Утверждение: |
Язык тандемных повторов [math] L = \{ww \mid w \in \Sigma^{*} \} [/math] не является КС-языком. |
| [math]\triangleright[/math] |
|
Это доказывается с помощью леммы о разрастании. |
| [math]\triangleleft[/math] |
| Утверждение: |
Дополнение к языку тандемных повторов [math]\overline{L}[/math] является КС-языком. |
| [math]\triangleright[/math] |
|
Для упрощения рассмотрим этот язык на бинарном алфавите [math]\Sigma = \{a,b\}[/math].
Для [math] \overline{L} [/math] можно составить следующую КС-грамматику [math]G[/math]:
- [math]S \to AB \mid BA[/math]
- [math]S \to A \mid B[/math]
- [math]S \to \varepsilon [/math]
- [math]A \to aAa \mid aAb \mid bAa \mid bAb \mid a [/math]
- [math]B \to aBa \mid aBb \mid bBa \mid bBb \mid b [/math]
Докажем этот факт.
Сначала заметим, что нетерминал [math]A[/math] порождает слова нечётной длины с центральным символом [math]a[/math]. В свою очередь нетерминал [math]B[/math] порождает слова нечётной длины с центральным символом [math]b[/math]. Таким образом, правило [math]S \to A \mid B[/math] порождает все возможные слова нечётной длины.
Докажем, что все слова, порождённые [math]G[/math], есть в [math]\overline{L}[/math].
[math]\varepsilon[/math], а также все слова нечётной длины не являются тандемными повторами.
Рассмотрим произвольное слово чётной длины, сгенерированное при помощи правила [math]S \to AB [/math]. Пусть его часть, соответствующая [math]A[/math], имеет длину [math]2N+1[/math], а часть, соответствующая [math]B[/math], — длину [math]2M+1[/math].
Таким образом, мы получили слово длины [math]2N+2M+2[/math]. Если оно является тандемным повтором, то символ, стоящий на позиции [math]N+1[/math], должен быть равен символу на позиции [math]2N+M+2[/math]. Но по построению это не так.
Для правила [math]S \to BA [/math] доказательство аналогично.
Докажем, что все слова из [math]\overline{L}[/math] порождаются [math]G[/math].
С помощью [math]G[/math] можно вывести [math] \varepsilon[/math], а также любое слово нечётной длины.
Далее рассмотрим произвольное слово чётной длины из [math]\overline{L}[/math]. Докажем, что его можно разбить на два слова нечётной длины, имеющие различные центральные символы. Предположим, что это не так, то есть такого разбиения нет.
Пусть это слово имеет длину [math]2N[/math]. Тогда рассмотрим все его префиксы нечётной длины. Их центры находятся на позициях [math]1, 2, \ldots ,N[/math], а центры соответствующих им суффиксов — на позициях [math]N+1, N+2, \ldots ,2N[/math]. Поскольку искомого разбиения не существует, то получается, что символ на позиции [math]1[/math] равен символу на позиции [math]N+1[/math], символ на позиции [math]2[/math] равен символу на позиции [math]N+2[/math], и так далее. Следовательно, первая половина слова равна его второй половине, т.е. оно является тандемных повтором.
Получили противоречие, следовательно любое слово чётной длины из [math]\overline{L}[/math] можно разделить на два слова нечётной длины с различными центральными символами. В свою очередь, такие слова могут быть сгенерированы при помощи грамматики [math]G[/math] и соединены при помощи правила [math]S \to AB \mid BA[/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] \mathrm{half}(L) = \{ w \mid ww \in L \} [/math] |
Операция [math] \mathrm{half} [/math] также не сохраняет КС-язык таковым. Покажем это на примере.
Рассмотрим язык [math] L = \{ a^n b a^n b a^m b a^l b a^k b a^k b \} [/math].
Заметим, что он может быть сгенерирован при помощи следующей КС-грамматики:
- [math] S \to AbBbBbAb [/math]
- [math] B \to a \mid aB[/math]
- [math] A \to b \mid aAa[/math]
Докажем, что [math] \mathrm{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] \mathrm{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], а, поскольку регулярные языки замкнуты относительно дополнения, то разность можно выразить через пересечение.
См. также
Источники информации
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — C. 302-304 : ISBN 5-8459-0261-4 (рус.)
