====== JFIZO - Zadanie 09.043 ======
  -$S(\epsilon, \epsilon, \epsilon)$
  -$S(s,t,w) \Rightarrow S(t,s,w)$
  -$S(s,t,w) \Rightarrow S(s, at, aw), a \in A$

**Wniosek 1**: $S(\epsilon, s, s)$\\

$L = \{w : S(s,t,w), s \in L_1, t \in L_2\}$

  *Jeśli $L_1$, $L_2$ regularne, to czy $L$ regularny?
  *Jeśli $L_1$, $L_2$ CFL, to czy $L$ CFL?

=====Regularny=====

Weźmy DFA $A$ i $B$, takie że $L(A)=L_1$ i $L(B)=L_2$.

Zbudujmy NDFA, którego $Q=Q_A\times Q_B$.\\
Funkcja przejścia to połączenie obu tych funkcji, tylko $\delta_A$ przesuwa lewą współrzędną, a $\delta_B$ prawą.\\
Stan akceptujący to taki, gdy obie współrzędne stanu są akceptujące w oryginalnych automatach.\\

Skonstruowaliśmy NDFA rozpoznający splecenie 2 jeżyków regularnych, a więc splecenie jeżyków regularnych jest regularne.

=====Bezkontekstowy=====
$L_1 = \{a^nca^n : n \in \mathbb{N}\}$
$L_2 = \{b^ndb^n : n \in \mathbb{N}\}$
Niech N - stała z lematu o pompowania dla splecenia języków $L_1$ i $L_2$.
Weźmy splecenie słów $a^Nca^N \in L_1$ i $b^Ndb^N \in L_2$ - $a^Nb^Ncda^Nb^N$. Nie popompujemy sobie, bo musimy pompować po obu stronach $c$ i $d$ oraz $a$ i $b$ naraz.