26
правок
Изменения
Новая страница: «В отличие от [[Замкнутость регулярных языков относительно различных операций|регулярны...»
В отличие от [[Замкнутость регулярных языков относительно различных операций|регулярных языков]], КС-языки не замкнуты относительно всех теоретико-множественных операций. К примеру, дополнение и пересечение КС-языков не обязательно являются КС-языками.
Здесь и далее считаем, что <tex> L_1 и L_2 </tex> -- КС языки.
= Операции с КС-языками =
== Объединение ==
{{ Утверждение
|statement= <tex> L_1 \cup L_2 </tex> также является КС-языком.
|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> S' \Rightarrow^{*} w \iff S \Rightarrow^{*} w \lor T \Rightarrow^{*} w </tex>. В левую сторону: коли <tex> S \Rightarrow^{*} w </tex> и есть правило <tex> S' \to S </tex>, то, по определению <tex> Rightarrow^{*} </tex> получаем, что <tex> S' \Rightarrow^{*} w </tex>. Аналогично и для <tex> T </tex>.
В обратную сторону, пусть <tex> S' \Rightarrow^{*} w </tex>. Поскольку <tex> S' \to S\,|\,T </tex> -- единственные правила, в которых нетерминал <tex> S' </tex> присутствует в правой части, а значит, либо <tex> S' \Rightarrow S \Rightarrow^{*} w </tex>, либо <tex> S' \Rightarrow T \Rightarrow^{*} w </tex>, что и требовалось доказать.
}}
== Конкатенация ==
{{ Утверждение
|statement= <tex> L_1 L_2 </tex> -- КС-язык.
|proof=КС-грамматика для <tex> L_1 L_2 </tex> выглядит следующим образом: <tex> S' \to S T </tex>, и <tex> S </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>.
}}
== Прямой и обратный гомоморфизм ==
== Разворот ==
== Циклический сдвиг ==
== Дополнение, пересечение и разность ==
= Операции над КС-языком и регулярным языком =
= Проверка непустоты КС-языка =
Здесь и далее считаем, что <tex> L_1 и L_2 </tex> -- КС языки.
= Операции с КС-языками =
== Объединение ==
{{ Утверждение
|statement= <tex> L_1 \cup L_2 </tex> также является КС-языком.
|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> S' \Rightarrow^{*} w \iff S \Rightarrow^{*} w \lor T \Rightarrow^{*} w </tex>. В левую сторону: коли <tex> S \Rightarrow^{*} w </tex> и есть правило <tex> S' \to S </tex>, то, по определению <tex> Rightarrow^{*} </tex> получаем, что <tex> S' \Rightarrow^{*} w </tex>. Аналогично и для <tex> T </tex>.
В обратную сторону, пусть <tex> S' \Rightarrow^{*} w </tex>. Поскольку <tex> S' \to S\,|\,T </tex> -- единственные правила, в которых нетерминал <tex> S' </tex> присутствует в правой части, а значит, либо <tex> S' \Rightarrow S \Rightarrow^{*} w </tex>, либо <tex> S' \Rightarrow T \Rightarrow^{*} w </tex>, что и требовалось доказать.
}}
== Конкатенация ==
{{ Утверждение
|statement= <tex> L_1 L_2 </tex> -- КС-язык.
|proof=КС-грамматика для <tex> L_1 L_2 </tex> выглядит следующим образом: <tex> S' \to S T </tex>, и <tex> S </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>.
}}
== Прямой и обратный гомоморфизм ==
== Разворот ==
== Циклический сдвиг ==
== Дополнение, пересечение и разность ==
= Операции над КС-языком и регулярным языком =
= Проверка непустоты КС-языка =
