129
правок
Изменения
м
В обратную сторону<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\,|\,T </tex> — единственные правила, в которых нетерминал <tex> S' </tex> присутствует в правой части, то это означает, что либо <tex> S' \Rightarrow S \Rightarrow^{*} w </tex>, либо <tex> S' \Rightarrow T \Rightarrow^{*} w </tex>, что и требовалось доказать.
Остальное доказательство аналогично случаю с объединением.
Для того, чтобы построить КС-грамматику для языка {{ Утверждение|statement= <tex> L^{R} = \{ w^{R} \mid w \in L \}</tex> контекстно-свободна.|proof= Для того, чтобы построить <tex> L^{R} </tex>, необходимо развернуть все правые части правил грамматики для <tex> L </tex>.
То, что <tex> L </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\,|\,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>.
}}
|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> соответственно.
}}
}}
=== [[Основные определения, связанные со строками#Гомоморфизм языков | Прямой и обратный гомоморфизм гомоморфизмы]] ===
[[Файл:Homo.png|300px|thumb|right]]{{ Утверждение|statement= КС-языки замкнуты относительно прямого гомоморфизма.В случае с [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм языков|прямым гомоморфизмом]] всё просто: строится proof=Построим КС-грамматикаграмматику, в которой каждый символ <tex> x \in \Sigma </tex> заменяется заменим на <tex> h(x) </tex>. }}
{{ Утверждение
|statement= КС-языки замкнуты относительно обратного гомоморфизма.
|proof=
Для доказательства замкнутости [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм языков|обратного гомоморфизма]] будем делать аналогично [[Замкнутость регулярных языков относительно различных операций|доказательству]] для регулярных языков. Построим [[Автоматы с магазинной памятью|МП-автомат]] для <tex> h^{-1}(L) = \{ w \mid h(w) \in L \} </tex> на основе МП-автомата для языка <tex> L </tex> (назовем его <tex> M </tex>). Новый автомат <tex> M' </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>w \in L \iff w^{R} \in L^{R}</tex>. Докажем (<tex>\Rightarrow</tex>) индукцией по длине порождения в грамматике <tex>L</tex>. В обратную сторону (<tex>\Leftarrow</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>.
}}
'''Пример разворота''':
{{ Утверждение
|statement= Язык тандемных повторов <tex> L = \{ww \mid w \in \Sigma^{*} \} </tex> не является КС-языком, однако .|proof=Это доказывается с помощью [[Лемма о разрастании для КС-грамматик|леммы о разрастании]]. }}{{ Утверждение|statement= Дополнение к языку тандемных повторов <tex> \overline{L} </tex> — является КС-языкязыком.
|proof=
Для упрощения рассмотрим этот язык на бинарном алфавите <tex>\Sigma = \{a,b\}</tex>.
Для <tex> \overline{L} </tex> можно составить следующую [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматику]] <tex>G</tex>:
