JFiZO - Lista 4
JFiZO - Zadanie 09.028
- L = \{w \in \{0, 1\}^* : |w|_0 \le |w|_1 \le 2|w|_0 \}
- G = <\{S\}, \{0, 1\}, S, P>
- S \rightarrow S0S1S | S1S0S | S0S1S1S | S1S0S1S | S1S1S0S | \epsilon
Tutaj chyba można olać leading
L(G) \subseteq L:
Zawsze dokładamy nic, zero i jeden, dwa zera i jeden. Co zapewnia nam warunek: |w|_0 \le |w|_1 \le 2|w|_0
L \subseteq L(G):
Zgadliście! Nie jest bezkontekstowy!
Dowód.
Najpierw przekrawamy ten język z regularnym (11^*0)^*1^*, innymi słowy rozpatrujemy takie słowa, które nie mają nietrywialnych bloków zer.
Teraz, niech n będzie SzLoP (stałą z lematu o pompowaniu) i bierzemy słowo w = (1^{2n+1}0)^{2n+1}. To oczywiście należy do naszego okrojonego języka. Zgodnie z LoP, możemy sobie pompować.
Zauważmy jednak, że jeżeli podzielimy w = xyvtz, to |yvt| \leq n, zatem do słowa yt wpadnie najwyżej jedno zero.
Mamy więc dwa przypadki:
1. w yt nie ma zer, czyli yt = 1^k, k \leq n.
Weźmy teraz w' = xvz (czyli „pompujemy” minus jeden raz).
Wtedy jest \frac{|w'|_1}{|w'|_0} = \frac{4n^2+4n+1-k}{2n+1} co nie wpada do przedziału [2m,2m+1].
2. w yt są zera, czyli |yt|_1 = k < n, |yt|_0 = 1.
Napompujmy teraz w z tym podziałem dwukrotnie, czyli weźmy w' = xyyyvtttz i znowu policzmy ten ułamek.
Widzimy, że \frac{4n^2+4n+1+2k}{2n+1+2} = \frac{(2n-1)(2n+3)+4+2k}{2n+3} < 2n, a także trywialnie >2n-1.
Sprzeczność w obu przypadkach
Jakieś pierdolenie, do tego niekompletne
Taki pomysł, proszę o weryfikację.
Najpierw z produkcji tworzę sobie graf (dwudzielny), w sposób następujący:
Niech na początku V = N, czyli wierzchołkami są nieterminale.
Niech N → P_1, N → P_2, \ldots, N → P_k będą wszystkimi produkcjami wychodzącymi z nieterminala N.
Wówczas tworzę wierzchołki etykietowane N_1, \ldots, N_k (dokładam k nowych) i rysuję krawędzie N → N_i.
Natomiast z N_i rysuję krawędzie prowadzące do wierzchołków etykietowanych nieterminalami występującymi w P_i.
Łatwo zauważyć, że jeżeli N –> w, to \exists i.N → N_i \wedge \forall M.N_i → M \Rightarrow M →* w' dla pewnych słów w'.
Teraz algorytm: w każdym momencie mam listę nieterminali N, z których da się wyprodukować słowo. Inicjuję ją, a następnie:
1. wybieram pewien N z tej listy
2. przeglądam krawędzie wchodzące do N. Niech M_i → N. Jeżeli
Iwan przy klawiaturze
Gramatyka to u mnie (V,\Sigma,P,S).
Zdefiniujmy sobie f(X):V→\mathbb{B} = True, jeśli \exists w \in \Sigma^* . X \Rightarrow^* w\ | False\ wpp.
Jak łatwo zauważyć, f(A)\ \mathit{wtw}\ \exists B_1B_2\ldots B_k.(A\rightarrow B_1B_2\ldots B_k)\in P \wedge \forall i\ .\ f(B_i).
f(x) = True,\ gdzie x\in \Sigma^*
Chcemy, aby f(S) = True.
I TERAZ rysujemy sobie graf dwudzielny tak jak napisano powyżej: po lewej zmienne i terminale, po prawej symbole oznaczające wszystkie prawe strony wszystkich produkcji. Krawędź w prawo oznacza „yields” (Sipser), krawędź w lewo oznacza „zawiera w sobie wystąpienie zmiennej”. A dalej to już widać: przy każdym {bycie z prawej} piszemy liczbę oznaczającą ilość krawędzi z niego wychodzących. Następnie z każdego terminalu rozdajemy po jednym punkcie jego poprzednikom. Byty z prawej, które dostały tyle punktów, ile potrzebowały, wciągają do gry następne symbole, dla których powtarzamy rozdawanie punktów itd., aż do osiągnięcia punktu stałego. Jeśli S został wciągnięty do gry, zwróć True. Else → False.
JFiZO - Zadanie 09.031
S \rightarrow \neg S | (S \Rightarrow S) | p | q
- S_0 \rightarrow S
- Neg \rightarrow \neg
- Lpar \rightarrow (
- Rpar \rightarrow )
- Rarr \rightarrow \Rightarrow
- S \rightarrow NegS
- S \rightarrow LparA_1
- A_1 \rightarrow SA_2
- A_2 \rightarrow RarrA_3
- A_3 \rightarrow SRpar
- S \rightarrow p
- S \rightarrow q
JFiZO - Zadanie 09.032
Zadanie 32. Czy język L_3 = \{ w \in \{0, 1, 2\}^* : \not \exists x \in \{0, 1, 2\}^* \, w = xx \} jest bezkontekstowy?
Twierdzenie. L_3 jest bezkontekstowy.
Dowód. Pokażemy gramatykę G, a następnie udowodnimy, że L(G) = L_3. Zbiorem produkcji gramatyki G będą następujące relacje:
S \to X \mid Y \mid Z \mid XY \mid XZ \mid YX \mid YZ \mid ZX \mid ZY
X \to 0 \mid a_1 X a_2 \quad a_1, a_2 \in \{0, 1, 2\}
Y \to 1 \mid a_1 Y a_2
Z \to 2 \mid a_1 Z a_2
- L(G) \subseteq L_3
- S \to X \mid Y \mid Z – długość jest nieparzysta, więc nie da się podzielić słów na połowy.
- S \to XY \quad w = w_1 0 w_2 \, w_3 1 w_4. Niech k = |w_1| = |w_2| i l = |w_3| = |w_4|. Widac zatem, ze |w| = 2\cdot(k + 1 + l). Jesli podzielimy w na polowy o takiej dlugosci, to w kazdej polowie na k-tej pozycji znajda sie dwa rozne symbole.
- L_3 \subseteq L(G). Weźmy najkrótsze słowo w z L, które nie da się wyprowadzić z G.
- |w| jest nieparzysta, więc można wyprowadzić z X, Y lub Z.
- |w| jest parzysta, więc można wyprowadzić z XY, XZ, etc.
Patrzymy na pierwsza pozycje, na ktorej sie roznia polowy, np. w = w_1 0 w_2 \, w_3 1 w_4. Niech k = |w_1| = |w_3| i l = |w_2| = |w_4|.
Mozemy slowo w rozbic na w_1 0 w_2' w_3' 1 w_4 takie, ze |w_2'| = |w_3| i analogicznie |w_3'| = |w_2|. Wtedy |w_1 0 w_2'| = 2k + 1 i |w_3' 1 w_4| = 2l + 1.
Poniewaz to sa slowa o dlugosci nieparzystej, to mozemy je wyprowadzic z X, Y lub Z, a cale slowo z S \to XY \mid \ldots \mid ZY.
Idea
Mamy słowo (bez straty ogólności) w postaci X^i1X^iX^k0X^k, gdzie X→ 0|1|2.
Skąd mamy pewność, że różnią się one na jednej pozycji?
X^i1X^iX^k0X^k = X^i1X^{i+k}0X^k = X^i1X^kX^i0X^k
Jest to słowo składające się z dowolnych i znaków, potem jedynki, dowolnych k znaków, dowolnych i znaków, zera, dowolnych k znaków.
Czyli słowa różniące się na i+1szej pozycji.
JFiZO - Zadanie 09.040
Załóżmy, że L - język tych palindromów nad alfabetem {0,1}*, które mają taką samą ilość zer i jedynek jest bezkontekstowy.
Rozważmy słowo w = 0^N1^{2N}0^N, gdzie N jest stałą z lematu o pompowaniu.
Jakikolwiek podział sztyx słowa „w” sobie nie wybierzemy to znajdziemy takie k, że sz^kty^ks nie należy do L,
ponieważ albo zaburzy nam się równowaga liczb albo palindromowość.
W jedną stronę jest to oczywiste, na mocy wiadomych twierdzeń z wykładu, zatem pozostaje pokazać implikację „bezkontekstowy ⇒ regularny”.
Niech n będzie SzLoP dla języka L.
Rozważmy języki: L' = \{w \in L: |w| < n\}, L_k = \{w \in L: |w| \geq n, |w|\%(n!) = k\}. Oczywiście, L = L' \cup \bigcup_k L_k.
No i teraz pokazujemy, że każdy z tych n!+1 języków jest regularny. Dla L' jest to oczywiste, jako że to język skończony.
Natomiast w przypadku L_k zauważamy, że 0^m \in L_k \Rightarrow 0^{n!+m} \in L_k, czyli w L_k są wszystkie słowa przystające do k modulo n! (lub jest on pusty), co pociągałoby oczywiście regularność tego języka.
Powyższa implikacja bierze się z LoP - jeżeli 0^m \in L_k, to możemy sobie to słowo napompować zerami (jako że m >= n) - nie większą ich jednak ilością niż n. Zatem możemy napompować tak dużo razy, aby się długość zwiększyła o n!. The end.
JFIZO - Zadanie 09.042
Zadanie. Czy L = \{ 0^n1^{n^2} : n \in N \} jest bezkontekstowy?
Nie jest.
Dowód. Załóżmy nie wprost, że L jest bezkontekstowy. Niech N będzie stałą z lematu o pompowaniu. Rozpatrzmy słowo w = 0^N1^{N^2} = sztyx. Musimy pompować zarówno zera jak i jedynki. Ani z ani y nie może zawierać zarówno jedynek jak i zer. z = 0^a, y = 1^b. Czy słowo sz^2ty^2x \in L? Przybyło a zer i b jedynek. Czy (N+a)^2 = N^2+b? (N+a)^2 = N^2 + 2Na + a. Wiemy, że b < N. Jeśli a = 0 to b = 0, sprzeczność. Jeśli a \not= 0 to b = 2Na + a \ge N, sprzeczność.
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.
