JFIZO - Zadanie 09.043

1. S(\epsilon, \epsilon, \epsilon)
2. S(s,t,w) \Rightarrow S(t,s,w)
3. 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?

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.

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.