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

Материал из Викиконспекты
Перейти к: навигация, поиск
(док-во для языка не тандемных повторов (вторая часть))
м (rollbackEdits.php mass rollback)
 
(не показаны 33 промежуточные версии 4 участников)
Строка 8: Строка 8:
  
 
{{ Утверждение
 
{{ Утверждение
|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>.
  
 
}}
 
}}
Строка 24: Строка 28:
 
|statement=  <tex> L_1 L_2 </tex> — КС-язык.
 
|statement=  <tex> L_1 L_2 </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> соответственно.
 
|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>.  
 
}}
 
}}
  
=== Прямой и обратный гомоморфизм ===
+
===Гомоморфизмы ===
 +
==== [[Основные определения, связанные со строками#Гомоморфизм языков | Прямой гомоморфизм]] ====
  
[[Файл:Homo.png|300px|thumb|]]
+
{{ Утверждение
 +
|statement= КС-языки замкнуты относительно прямого гомоморфизма.
 +
|proof=
 +
Построим КС-грамматику, в которой каждый символ <tex> x \in \Sigma </tex> заменим на <tex> \mathrm{h}(x) </tex>.
 +
}}
  
В случае с [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм языков|прямым гомоморфизмом]] всё просто: строится КС-грамматика, в которой каждый символ <tex> x \in \Sigma </tex> заменяется на <tex> h(x) </tex>.  
+
==== [[Основные определения, связанные со строками#Гомоморфизм языков | Обратный гомоморфизм]] ====
 
+
{{ Утверждение
Для доказательства замкнутости [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм языков|обратного гомоморфизма]] будем делать аналогично [[Замкнутость регулярных языков относительно различных операций|доказательству]] для регулярных языков. Построим [[Автоматы с магазинной памятью|МП-автомат]] для <tex> h^{-1}(L) = \{ w \mid h(w) \in L \} </tex> на основе МП-автомата для языка <tex> L </tex> (назовем его <tex> M </tex>). Новый автомат <tex> M' </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> c </tex>.
# Сохраняем <tex> h(c) </tex> в буфере (входная лента для автомата <tex> M </tex>).
+
# Сохраняем <tex> \mathrm{h}(c) </tex> в буфере (входная лента для автомата <tex> M </tex>).
 
# Запускаем <tex> M </tex> на слове, находящемся в буфере.  
 
# Запускаем <tex> M </tex> на слове, находящемся в буфере.  
 
# После того, как <tex> M </tex> обработал весь буфер, переходим к пункту 1.
 
# После того, как <tex> M </tex> обработал весь буфер, переходим к пункту 1.
Строка 51: Строка 62:
 
* <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> 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' </tex> определяется следующими правилами:
** <tex> \delta'((q, \varepsilon), c, X) = \{((q, h(c)), X) \mid c \in \Sigma, q \in Q, X \in \Gamma \}</tex>. Когда буфер пуст, <tex> M' </tex> может прочитать свой следующий входной символ <tex> c </tex> и поместить <tex> h(c) </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> (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> (s, \varepsilon) </tex>, т.е. <tex> M' </tex> стартует в начальном состоянии <tex> M </tex> с пустым буфером.
 
* Допускающими состояниями <tex> M' </tex> являются состояния <tex> (q, \varepsilon)</tex>, где <tex> q \in T </tex>.
 
* Допускающими состояниями <tex> M' </tex> являются состояния <tex> (q, \varepsilon)</tex>, где <tex> q \in T </tex>.
Таким образом получаем, что <tex>(s, 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> h^{-1}(L) </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>.
 +
}}
  
 
=== Разворот ===
 
=== Разворот ===
  
Для того, чтобы построить КС-грамматику для языка <tex> L^{R} = \{ w^{R} \mid w \in L \} </tex>, необходимо развернуть все правые части правил грамматики для <tex> 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>\Leftarrow</tex>) рассуждения аналогичны.
+
Покажем, что <tex>w \in L \iff w^{R} \in L^{R}</tex>.  
  
'''База'''. <tex>A \underset{L}{\Rightarrow} w</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>L</tex> существует правило <tex>A \rightarrow w</tex> и, так как мы развернули все правые части правил, то <tex>A \underset{L^{R}}{\Rightarrow} w^{R}</tex>.
  
'''Предположение индукции'''. Пусть <tex>A \underset{L}{\Rightarrow}^* w</tex> менее чем за <tex>n</tex> шагов, тогда <tex>A \underset{L^{R}}{\Rightarrow}^* w^{R}</tex>.
+
:'''Предположение индукции'''. Пусть <tex>A \underset{L}{\Rightarrow}^* w</tex> менее чем за <tex>n</tex> шагов, тогда <tex>A \underset{L^{R}}{\Rightarrow}^* w^{R}</tex>.
  
'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A \underset{L}{\Rightarrow}Y_1 Y_2...Y_m \underset{L}{\Rightarrow}^*w</tex>, где <tex> Y_i \in N \cup \Sigma </tex>. Цепочку <tex> w </tex> можно разбить на <tex>w_1 w_2...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...Y_m</tex>, то <tex>A \underset{L^{R}}{\Rightarrow}Y_m Y_{m - 1}...Y_1</tex>, откуда следует, что <tex> A \underset{L^{R}}{\Rightarrow}^* w^{R} </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>\Leftarrow</tex>
 +
:Доказательство аналогично.
 +
}}
 +
'''Пример разворота''':
  
В отличие от регулярных языков, дополнение до КС-языка, пересечение КС-языков и разность КС-языков может не быть КС-языком.
+
Пусть задана КС-грамматика <tex>G</tex> для языка <tex>L = a^i b^j c^i</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=
 
+
Это доказывается с помощью [[Лемма о разрастании для КС-грамматик|леммы о разрастании]].  
То, что <tex> L </tex> — не КС-язык, доказывается с помощью [[Лемма о разрастании для КС-грамматик|леммы о разрастании]].  
+
}}
 
+
{{ Утверждение
 +
|statement= Дополнение к языку тандемных повторов <tex>\overline{L}</tex> является КС-языком.
 +
|proof=
 +
Для упрощения рассмотрим этот язык на бинарном алфавите <tex>\Sigma = \{a,b\}</tex>.
 
Для <tex> \overline{L} </tex> можно составить следующую [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]] <tex>G</tex>:
 
Для <tex> \overline{L} </tex> можно составить следующую [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]] <tex>G</tex>:
  
Строка 91: Строка 125:
 
Докажем этот факт.
 
Докажем этот факт.
  
Сначала заметим, что нетерминал <tex>A</tex> порождает слова нечётной длины с центральным символом <tex>a</tex>. В свою очередь нетерминал <tex>B</tex> порождает слова нечётной длины с центральным символом <tex>b</tex>. Таким образом, правило <tex>S \to A \mid B</tex> порождает все слова нечётной длины.
+
Сначала заметим, что нетерминал <tex>A</tex> порождает слова нечётной длины с центральным символом <tex>a</tex>. В свою очередь нетерминал <tex>B</tex> порождает слова нечётной длины с центральным символом <tex>b</tex>. Таким образом, правило <tex>S \to A \mid B</tex> порождает все возможные слова нечётной длины.
  
1. '''Докажем, что все строки, порождённые <tex>G</tex>, есть в <tex>\overline{L}</tex>.'''
+
'''Докажем, что все слова, порождённые <tex>G</tex>, есть в <tex>\overline{L}</tex>.'''
  
 
<tex>\varepsilon</tex>, а также все слова нечётной длины не являются тандемными повторами.
 
<tex>\varepsilon</tex>, а также все слова нечётной длины не являются тандемными повторами.
  
Рассмотрим произвольное слово чётной длины, сгенерированное при помощи правила <tex>S \to AB </tex>. Пусть его часть, соответствующая <tex>A</tex>, имеет длину <tex>2N+1</tex>, а часть, соответствующая <tex>B</tex>, - длину <tex>2M+1</tex>.  
+
Рассмотрим произвольное слово чётной длины, сгенерированное при помощи правила <tex>S \to AB </tex>. Пусть его часть, соответствующая <tex>A</tex>, имеет длину <tex>2N+1</tex>, а часть, соответствующая <tex>B</tex>, {{---}} длину <tex>2M+1</tex>.  
  
 
[[Файл:TandemRepeatAB.png]]
 
[[Файл:TandemRepeatAB.png]]
Строка 105: Строка 139:
 
Для правила <tex>S \to BA </tex> доказательство аналогично.
 
Для правила <tex>S \to BA </tex> доказательство аналогично.
  
2. '''Докажем, что все строки из <tex>\overline{L}</tex>, порождаются <tex>G</tex>.'''   
+
'''Докажем, что все слова из <tex>\overline{L}</tex> порождаются <tex>G</tex>.'''   
  
 
С помощью <tex>G</tex> можно вывести <tex> \varepsilon</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>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>\overline{L}</tex> можно разделить на два слова нечётной длины с различными центральными символами. В свою очередь, такие слова могут быть сгенерированы при помощи грамматики <tex>G</tex> и соединены при помощи правила  <tex>S \to AB \mid BA</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> \mathrm{half}(L) = \{ w \mid{wx \in L ,|w|=|x|}\}</tex>
+
<tex> \mathrm{half}(L) = \{ w \mid ww \in L \} </tex>
 
}}
 
}}
  
Операция <tex> \mathrm{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> \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>. Отсюда следует, что:
+
{{ Утверждение
 +
|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>
Строка 144: Строка 198:
  
 
А значит, <tex> n = l = k = m </tex>, и <tex> \mathrm{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 допуском по допускающему состоянию. Построим прямое произведение этих автоматов так же, как строилось прямое произведение для двух ДКА.
 
Пусть регулярный язык задан своим [[Детерминированные конечные автоматы|ДКА]], а КС-язык — своим [[Автоматы с магазинной памятью|МП-автоматом]] c допуском по допускающему состоянию. Построим прямое произведение этих автоматов так же, как строилось прямое произведение для двух ДКА.
Строка 163: Строка 219:
  
 
Этот автомат использует в качестве состояний пары из двух состояний каждого автомата, а за операции со стеком отвечает только МП-автомат. Слово допускается этим автоматом <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>
  
Разность КС-языка и регулярного языка выражается следующим образом: <tex> L \setminus R = L \cap \overline{R} </tex>, а, поскольку регулярные языки замкнуты относительно дополнения, то разность можно выразить через пересечение.
+
Регулярные языки замкнуты относительно дополнения, следовательно разность можно выразить через пересечение.
 
+
}}
 
== См. также ==
 
== См. также ==
 
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
 
* [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
 
+
* [[Замкнутость регулярных языков относительно различных операций]]
 +
* [[Основные определения, связанные со строками]]
 
== Источники информации ==
 
== Источники информации ==
  
Строка 177: Строка 238:
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Базовые понятия о грамматиках]]

Текущая версия на 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 (рус.)