JFiZO - Lista 1
JFiZO - Zadanie 09.001
Z dedykacją dla driksa, chociaż jest pałkossaczem.
Załóżmy sobie nie wprost, że istnieje automat A, o |Q_A|<1024, rozpoznający L.
Weźmy w,x\in L, w\not=x takie, że \delta(w,q_0)=\delta(x,q_0). (Jak się robi deltę z daszkiem? Na bazy się spieszę, nie mam czasu googlać.) Takie w i x istnieją, bo każde słowo zwraca jakiś stan, a stanów jest mniej niż słów \geq10-znakowych.
Tedy istnieje taka pozycja i, na której słowa się różnią: w_i \not = x_i.
Dla ustalenia uwagi przyjmijmy, że w_i=0, a x_i=1.
Weźmy więc sobie dowolne y\in \Sigma^* długości |y|=10-i.
A wtedy wy\in L i xy\not\in L, ale przecież \delta(wy,q_0)=\delta(xy,q_0). Sprzeczność :( (again, nie dałem daszków nad deltami)
Oczywiście pytania typu „a czemuuu…” w komentarzach mile widziane.
JFiZO - Zadanie 09.002
Niech n będzie stałą z lematu o pompowaniu dla języka L.
Wtedy słowo a^nb^{2n} możemy podzielić na xyz, |xy|\leq n jedynie tak, że xy będzie ciągiem liter a.
Czyli y również będzie ciągiem (niepustym, z założenia w lemacie) liter a (niechaj m=|y|), więc xy^2z=a^{n+m}b^{2n} powinno należeć do L, a nie należy, gdyż dla żadnego m naturalnego dodatniego nie jest n+m=n. Sprzeczność.
JFiZO - Zadanie 09.003
- Rozwiązanie w Hopcroft, Przykład 3.2, strony 72-73
Treść
Zbiór L tych słów nad \lbrace 0,1 \rbrace, które są liczbą pierwszą w zapisie binarnym nie jest regularny.
Lemat 1
Ten lemat nie dowodzi równoważności regularności tych języków. Bez tego lematu dowód na dole nic nie daje.
— Alistra 2010/03/07 21:55
Niech N = \{ 1^n | n - prime \} nad {1}.
Każde słowo z N ma równoważne sobie słowo w L. (== jęzki N i L są równoważne?)
Dowód \Leftarrow.
f(l_1l_2…l_n \in L) = 1^{\sum_{i=1}^{i=n}2^il_i} \in N
Dowód \Rightarrow.
f^{-1}(1^n \in N) = l_1l_2…l_m \in L t.że l_1l_2…l_m = n w zapisie binarnym.
Dowód
Pokażemy, że N nie jest regularny.
Załóżmy niewprost, że N jest regularny. Istnieje więc p t.że dla każdego s = xyz = 1^n \in N, |s| >= p zachodzi xy^iz \in N.
Niech:
- |x| = len_x, |y| = len_y, |z| = len_z
- Skoro xyz \in N to prime(len_x + len_y + len_z) == true.
- Skoro N jest regularny, to prime(len_x + len_y * i + len_z) == true
- Niech i = len_x + len_z + 2*len_y + 2, wtedy:
len_x + len_z + i * len_y =
(len_x + len_z) + (len_x + len_z + 2*len_y + 2) * len_y =
(len_x + len_z) + (len_x + len_z) * len_y + (2*len_y + 2) * len_y =
(len_x + len_z) * (1 + len_y) + 2 * (len_y + 1) * len_y =
(1 + len_y) * (len_x + len_z + 2 * len_y).
- len_y \geq 1 z lematu o pompowaniu. Rozłożyliśmy więc liczbę pierwszą na składniki > 1. Sprzeczność.
JFiZO - Zadanie 09.004
Niech L będzie dowolnym podzbiorem 0^∗ . Udowodnij, że L^∗ jest językiem regularnym.
Rozwiązanie. Rozpatrzmy dowolny język L \subseteq 0^∗ . Rozważmy trzy przypadki:
- L jest pusty. Wtedy L^∗ jest regularny.
- L jest niepusty i zawiera wyłącznie słowo puste. Wtedy L^∗ również składa się wyłącznie ze słowa pustego – jest więc regularny.
- L jest niepusty i istnieje najkrótsze niepuste słowo v. Niech n = |v| i niech L_k = \lbrace w : w \in L^∗ oraz |w| \mbox{ mod } n = k \rbrace. Pokażemy, że dla każdego k język L_k jest regularny, co znaczy, że L^∗ jest regularny (jako suma skończenie wielu języków regularnych). Weźmy dowolne k. Rozważmy przypadki:
- L_k jest pusty. Wtedy oczywiście L_k jest regularny,
- L_k nie jest pusty – wtedy istnieje najkrótsze słowo v', które należy do języka L_k. Do języka L_k należą więc wszystkie wyrazy długości |v'| + ln, gdzie l \in \mathbb{N} (do każdego wyrazu możemy „dokleić” dowolną ilość razy wyraz v o długości n). Co oznacza, że L_k jest regularny, ponieważ opisuje go wyrażenie v'(0^n)^∗.
Przykład.
- L = \{aaa, aaaaa, aaaaaaa\}
- n = 3
- L^* = \{a^3, a^5, a^6, a^7, a^8, a^9, a^{10}, a^{11}, …\}
- L_k = \{w : w \in L^* |w| mod 3 = k\}
- L_0 = \{a^3, a^6, a^9, …\}
- L_1 = \{a^7, a^{10}, a^{13}, …\}
- L_2 = \{a^5, a^8, a^{11}, …\}
- Każde L_k ma kolejne elementy o długości |v'| + ln, ponieważ do v' możemy doklejać wyraz n z języka L.
JFiZO - Zadanie 09.007
13 stanów. Konstrukcja trywialna. Szkic dowodu: rozważmy język sufiksów najwyżej 4-znakowych wyrazów naszego języka (czyli \epsilon, a, aa, aaa, \ldots). Podobnie jak w zadaniu 001, pokażmy że automat nie może mieć mniej niż 13 stanów.
Hopcroft strona 81-82
