1109144854

Zadanie 33. Udowodnij, że dla każdej liczby naturalnej k istnieje język L C {a, b. c}* dający się rozpoznawać deterministycznym automatem skończonym o mniej niż kK² stanach i taki, że język L^_ck nie daje się rozpoznawać deterministycznym automatem skończonym o mniej niż 2^kK stanach, gdzie K = 2^k.

Wskazówka: Być może przyda nam się pamiętać, że suma n liczb pierwszych jest zawsze mniejsza niż n²logn, zaś ich iloczyn zawsze jest większy od 2^nlogn.

4 Więcej zadań o językach regularnych

Przez język rodzynkowy będziemy przez chwilę (to znaczy w kolejnych trzech zadaniach i ani chwili dłużej) rozumieć język będący podzbiorem L_a*ba

Dla danego języka regularnego L napis i(L) będzie oznaczał na tej liście indeks języka L, czyli minimalną liczbę stanów deterministycznego automatu rozpoznającego L.

Zadanie 34. Czy istnieje język rodzynkowy L taki, że L* jest bezkontekstowy ale nie jest regularny?

Zadanie 35. Dla ustalonego n naturalnego niech L_n będzie językiem składającym się ze wszystkich słów postaci a^lba^, gdzie 0 < i,j < 2n oraz \i — j\ < 1. Udowodnij, że i(L*) szacuje się (z dokładnością do stałej multiplikatywnej) przez n² .

Wskazówka: Warto rozważyć słowa postaci a^k{ba²ⁿ)¹, dla odpowiednich liczb kil.

Zadanie 36. Udowodnij, że dla każdego naturalnego n istnieje język rodzynkowy L_n, taki że i(L_nL_n) > c2ⁱ(L_n), gdzie c jest pewną stałą niezależną od n. Jeśli nie potrafisz pokazać takiego wykładniczego dolnego ograniczenia na wzrost i(L_nL_n), to dostaniesz punkty również za inne ograniczenie, jeśli nie będzie mniejsze niż ci(L_n)³.

Relacje automatyczne. W przeciwieństwie do wielu innych pojęć, które czasem na tej liście zadań zdarza nam się definiować, pojęcie relacji automatycznych jest standardowe i systematycznie badane. Standardowa definicja jedynie nieznacznie odbiega od naszej.

Zdefiniujmy funkcję l : {0,1}* —* N jako: l(e) = 0, l(0w) = 2l(w), l(lw) = 2l(w) + 1.

Dla liczby naturalnej k zdefiniujmy S* = {0, l}^fc.

Dla liczb naturalnych j < k zdefiniujmy funkcję II: T,*_k —* {0,1}* jako: n£(e) = e, njfc((ai,a2, -.. aj,... ak)w) = Ojll^(w), gdzie (01,02? - • •    • • • o/c) G E*,.

Relację R C N^fe nazwiemy na tej liście zadań automatyczną, jeśli język Lr złożony z tych słów w G ££, dla których zachodzi R(l(H_k(w)), l(U].(w)),... l(TL^k(w))), jest regularny.

Zadanie 37. Czy relacja dodawania jest automatyczna? Przez relację dodawania rozumiemy tu {(a, b, c) G N³ : a + b = c}.

Zadanie 38. Czy relacja mnożenia jest automatyczna? Przez relację mnożenia rozumiemy tu {(a, b, c) G N³ : ab = c}.

Zadanie 39. Udowodnij, że rzut relacji automatycznej jest relacją automatyczną. Innymi słowy, jeśli R Q N^k jest relacją automatyczną, to również relacja R' = {r G N^fe_1 : 3m G N (r, m) G R} jest relacją automatyczną (dla uproszczenia możesz przyjąć, że k = 2).

5