8299308546

Zadanie 32. a. Jaką minimalną liczbę stanów musi mieć deterministyczny automat skończony rozpoznający M_n ?

b. Jaką minimalną liczbę stanów musi mieć niedeterministyczny automat skończony rozpoznający M_n ?

Zadanie 33. Udowodnij, że każdy niedeterministyczny automat skończony rozpoznający język M_n musi mieć więcej niż 2^~^l stanów.

Wskazówka. Dla liczby naturalnej k, takiej, że 1 < k < n/2 nazwijmy parę liczb {2k — 1,2k} rodziną. Powiemy że słowo x € {1,2, ...n}* nie rozdziela rodzin, jeśli zawsze wtedy, gdy jedna z liter z jakiejś rodziny występuje w słowie x, w słowie tym występuje również druga z tych liczb. Powiemy że słowo x jest rosnące, gdy każda jego kołejna litera jest liczbą większą niż poprzednia. Ile jest słów nie należących do M_n, które są rosnące i nie rozdzielają rodzin?

Na potrzeby kolejnych trzech zadań zdefiniujmy indukcyjnie następującą ternarną relację © na słowach nad alfabetem E:

•    ©(e,e,e)

•    Q(aw,v,ax) jeśli Q(w,v,x)

•    Q(w,av,ax) jeśli Q(w,v,x)    gdzie a G E and w,v,x € E*

Dla języka L C E* i słowa w € E* zdefiniujmy:

Lsw = {x € E* : 3y e E* (©(w, x, y) A y € L)}

Ly_w = {x € E* : Vy € E* (©(w, x,y) => y e L)}

Zadanie 34. Załóżmy, że L jest językiem regularnym, zaś w jest pewnym ustalonym słowem z E*. Czy wynika z tego że L\/_w jest językiem regularnym ?

Zadanie 35. Załóżmy, że L jest językiem regularnym, zaś w jest pewnym ustalonym słowem z E*. Czy wynika z tego że L^_w jest językiem regularnym ?

Zadanie 36. 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 pierwszych n liczb pierwszych jest zawsze mniejsza niż n²logn, zaś ich iloczyn zawsze jest większy od 2^nlogn.

6 Zadania o hipotezie Cernego

Kolejne zadania mają związek z - otwartą od pół wieku - hipotezą Cernego. Mówi ona, że jeśli zbiór sync(Q) jest niepusty, to zawiera on jakieś słowo o długości nie większej niż (|Q| — l)² (znany jest automat, z niepustym sync(Q), dla którego najkrótsze słowo w sync(Q) ma długość dokładnie (|Q| — l)²)-

Definicja. Dla danego deterministycznego automatu skończonego A = (E, Q, go, F, S) i zbioru S C Q, przez sync(S) oznaczmy zbiór {w € E* : Vg, q' € S S(q,w) = 5(q',w)}. Zauważ, że definicja nie zależy od wyboru stanów qo i F & tylko od zbioru stanów Q, od alfabetu E i od funkcji przejścia 6.

5