пометка: если хотите подробнее что-то узнать по теории. На странице 75, параграф 17 в книге Замятин, Шур всё описано.

Определение

Пусть $L \subseteq \Sigma^$ Подстановкой наз-ся $\tau : \Sigma \to \mathscr{B}(\triangle^)$ [пометка: $\tau$ берёт букву из $\Sigma$ и отображает над алфавитом $\triangle$], которое обладает свойствами:

1. $w = a_1 … a_n$ $\tau(w) = \tau(a_1) … \tau(a_n)$
2. $L = \bigcup\{w\}, w \in L$ $\tau(L) = \bigcup \tau(w), w \in L$
3. $\tau(\varepsilon) = \varepsilon$

Примеры:

1. $L = \{a,b\}$ $L_1, L_2 \sube \triangle^*\ \ \ \ \tau(a) = L_1, \tau(b)=L_2$ $\tau(L) = \tau(a) + \tau(b) = L_1 + L_2$
2. $L = \{a,b\}$ $\tau(L) = \tau(a)\tau(b) = L_1L_2$
3. $L = a^* = \varepsilon + a + aa + …$ $\tau(L) = \varepsilon + L_1 + L^2_2 + L^3_1 + …. = L^*_1$
4. $\tau(a) = U_1$, $\tau(b) = U_2$ $L(a+b)^$ $\tau(L) = (U_1 + U_2)^$

Теорема о подстановке

<aside> 📌 Пусть $L \subseteq \Sigma^$ - контекстносвободный язык, подстановка $\tau: \Sigma \to \mathscr{B}(\triangle^)$ $\forall a \in \Sigma$ $\tau(a)$ - контекстносвободный язык Тогда $\tau(L)$ - контекстносвободный язык

</aside>

Доказательство:

$\Sigma = \{a_1, … a_m\}$ L - контекстносвободная $\exists \ G = (Г_G, \Sigma, P_G, S_G)$ порождает $L$ $\tau(a_i)$ - контекстносвободный язык $\exists \ G_i = (Г_i, \triangle, P_i, S_i)$, которая порождает $\tau(a_i) = L_i$

Строим грамматику $H = (\widehat{Г}, \triangle, \widehat{P}, S_G)$

$\widehat{Г} = Г_G \bigcup(\bigcup^m_{i=1} Г_i)$

Строим $\widehat{P} = \bigcup^m_{i=1}P_i$

Пусть $A \to \alpha \in P_G$, заменим все терминалы в $\alpha$ на соответствующие аксиомы грамматики $S_i$

т.к. $a_i$ входит в $\alpha$ - заменяем её на $S_i$ и добавим в $\widehat{B}$

Докажем, что $\tau(L) = L(H)$

$w \in \tau(L) = \bigcup \tau(u), w \in L$

$\exists u \in L$ $w \in \tau(u) = \tau(a_1, … a_m) = \tau(a_1) …. \tau(a_m)$

$\Leftrightarrow w=w_1 \ w_2 \ … \ w_m \Leftrightarrow \forall i \exists S_i \rArr_{G_i} w_i$ (пометка: $w_1 \in \tau(a_1), …. w_m \in \tau(a_m)$)

$u = a_1, … a_m \in L \Leftrightarrow S_G \rArr_G a_1 … a_m$

$S_H \rArr^_H S_1 … S_m \rArr^_H w_1 \ w_2 … w_m = w \in L(H)$

Доказательство (в обратную сторону):

$w \in L(H)$

$S_G \rArr^_H w \in \triangle^$

$S_G \rArr^_H S_1 S_2 … S_m \rArr^_H w_1 \ w_2 … w_m$ $\in \tau(u)$

соответвует

$S_G \rArr^*_G a_1 \ a_2 … a_m \in L$

#Пример 1

$L = \{a,b\}$ $G_1 = (Г_1, \triangle, P_1, S_1) \to L_1$

                               $G_2 = (Г_2, \triangle, P_2, S_2) \to L_2$

$G^{(1)}$ $S \to a|b$ Заменим на $\{S \to S_1|S_2\} \bigcup P_1 \bigcup P_2$

#Пример 2

$G^{(2)}$ $L = \{a, b\}$ Заменим на $\{S \to S_1\} \bigcup P_1 \bigcup P_2$

#Пример 3

$L = a^*$

$G^{(3)}$ $S \to aS|\varepsilon$ Заменим на $\{S \to S, S|\varepsilon\} \bigcup P$