1632
правки
Изменения
м
rollbackEdits.php mass rollback
|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\,|\,mid T </tex>.
Покажем, что <tex> S' \Rightarrow^{*} w \iff S \Rightarrow^{*} w \lor T \Rightarrow^{*} w </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^{*} = \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' \, | \, mid \varepsilon </tex>.
}}
|statement= КС-языки замкнуты относительно прямого гомоморфизма.
|proof=
Построим КС-грамматику, в которой каждый символ <tex> x \in \Sigma </tex> заменим на <tex> \mathrm{h}(x) </tex>.
}}
|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> 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>.
}}
=== Разворот ===
:'''Переход'''.
:: Пусть в порождении <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> A \to Ab \mid \varepsilon </tex>
* <tex> B \to cBa \mid A </tex>
=== Дополнение к языку тандемных повторов ===
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Базовые понятия о грамматиках]]
