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

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

Текущая версия на 19:29, 4 сентября 2022

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

Здесь и далее считаем, что [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 \mid 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 \mid 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' \mid \varepsilon [/math].
[math]\triangleleft[/math]

Гомоморфизмы

Прямой гомоморфизм

Утверждение:
КС-языки замкнуты относительно прямого гомоморфизма.
[math]\triangleright[/math]
Построим КС-грамматику, в которой каждый символ [math] x \in \Sigma [/math] заменим на [math] \mathrm{h}(x) [/math].
[math]\triangleleft[/math]

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

Утверждение:
КС-языки замкнуты относительно обратного гомоморфизма.
[math]\triangleright[/math]
Homo.png

Докажем аналогично соответствующему утверждению для регулярных языков. Построим МП-автомат для [math] \mathrm{h^{-1}}(L) = \{ w \mid \mathrm{h}(w) \in L \} [/math] на основе МП-автомата для языка [math] L [/math] (назовем его [math] M [/math]). Новый автомат [math] M' [/math] будет действовать следующим образом:

  1. Если входное слово закончилось, допускаем или не допускаем его по допускающему состоянию.
  2. Считываем символ [math] c [/math].
  3. Сохраняем [math] \mathrm{h}(c) [/math] в буфере (входная лента для автомата [math] M [/math]).
  4. Запускаем [math] M [/math] на слове, находящемся в буфере.
  5. После того, как [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, \mathrm{h}(c)), X) \mid c \in \Sigma, q \in Q, X \in \Gamma \}[/math]. Когда буфер пуст, [math] M' [/math] может прочитать свой следующий входной символ [math] c [/math] и поместить [math] \mathrm{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, \mathrm{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] \mathrm{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]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 \ldots Y_m \underset{L}{\Rightarrow}^*w[/math], где [math] Y_i \in N \cup \Sigma [/math]. Цепочку [math] w [/math] можно разбить на [math]w_1 w_2 \ldots 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 \ldots Y_m[/math], то [math]A \underset{L^{R}}{\Rightarrow}Y_m Y_{m - 1} \ldots Y_1[/math], откуда следует, что [math] A \underset{L^{R}}{\Rightarrow}^* w^{R} [/math].

[math]\Leftarrow[/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].

TandemRepeatAB.png

Таким образом, мы получили слово длины [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 \} \{ c^j \}, L_2 = \{ a^i \} \{ 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]\triangleright[/math]
[math] L_1 \setminus L_2 = L_1 \cap \overline{L_2} [/math]
[math]\triangleleft[/math]

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

Половины тандемных повторов

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


Утверждение:
Операция [math] \mathrm{half} [/math] не сохраняет КС-язык таковым.
[math]\triangleright[/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], и по лемме о разрастании КС-языком не является.
[math]\triangleleft[/math]

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

Пересечение

Утверждение:
Пересечение КС-языка и регулярного языка — КС-язык.
[math]\triangleright[/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]\triangleleft[/math]

Разность

Утверждение:
Разность КС-языка и регулярного языка — КС-язык.
[math]\triangleright[/math]

[math] L \setminus R = L \cap \overline{R} [/math]

Регулярные языки замкнуты относительно дополнения, следовательно разность можно выразить через пересечение.
[math]\triangleleft[/math]

См. также

Источники информации

  • Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — C. 302-304 : ISBN 5-8459-0261-4 (рус.)