8299308546
Zadanie 32. a. Jaką minimalną liczbę stanów musi mieć deterministyczny automat skończony rozpoznający Mn ?
b. Jaką minimalną liczbę stanów musi mieć niedeterministyczny automat skończony rozpoznający Mn ?
Zadanie 33. Udowodnij, że każdy niedeterministyczny automat skończony rozpoznający język Mn 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 Mn, 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)}
Lyw = {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ż kK2 stanach i taki, że język L^ck nie daje się rozpoznawać deterministycznym automatem skończonym o mniej niż 2kK stanach, gdzie K = 2k.
Wskazówka: Być może przyda nam się pamiętać, że suma pierwszych n liczb pierwszych jest zawsze mniejsza niż n2logn, zaś ich iloczyn zawsze jest większy od 2nlogn.
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)2 (znany jest automat, z niepustym sync(Q), dla którego najkrótsze słowo w sync(Q) ma długość dokładnie (|Q| — l)2)-
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
Wyszukiwarka
Podobne podstrony:
75142 Skrypt PKM 1 00148 296 Odpowiedź: Zadanie 8.32 Jaką silą W należy działać na szczęki hamulca b
Skrypt PKM 1 00087 174 Zadanie 4.30 Jaką średnicę musi mieć sworzeń, aby naciski na zwojach gwintu i
50879 Skrypt PKM 1 00087 174 Zadanie 4.30 Jaką średnicę musi mieć sworzeń, aby naciski na zwojach gw
Zadanie 26. Jaką wartość musi mieć siła F2, aby układ znajdował się w równowadze? © 25
41647 skanuj0001 (336) ł. Oblicz, jaką gęstość musi mieć płuczka wiertnicza podczas wiercenia,a by p
Kangurek 2008 zadania 029 __A Ą /Xr% Matematyka z wesołym Kangurkiem >3 r~L!x^ 6. Jaką największ
skanuj0001 (336) ł. Oblicz, jaką gęstość musi mieć płuczka wiertnicza podczas wiercenia,a by przeciw
egz 2 Sera 2 zaoczne 20.06.2008 1. Jaką minimalną energię powinien mieć kwart promieniowania, żeby p
Zadanie 2.2 (3 pkt.) Z jakiej minimalnej wysokości musi się bez tarcia stoczyć kulka, aby przebyć tę
P230112 40 1 Uts,fa 1 i V m W ! 1_ si^ Zad.l. Jaką minimalną grubość musi posiadać
stata(1) Zadania: Zad2. Dla następujących liczb stanowiących jedną próbę: 3,1,5,5,1 podaj: a) liczbę
Nowe skanowanie 20130610124357 00007 Zadanie 32. Podczas szlifowania twardych gatunków drewna, na st
b) wyjaśnij, jaką właściwość musi mieć układ (otwarty, zamknięty, izolowany, adiabatyczny), by zasad
img038 (47) 32 Struktura sieci2.5. Co kryje się w warstwach ukrytych? Wiesz już, że każda sieć feedf
Nowe skanowanie 20130610124251 00005 Zadanie 28. Zaprojektowano pomieszczenie jadalni typu I dla 10
więcej podobnych podstron