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.
Dyskusja
Oczywiście jest tu błąd i oczywiście nikt przez rok go nie zauwazył:/ Jeśli w i x mają po 30 znaków i różnią się na pierwszym, to tu się wszystko wywala. Ale możnaby rozważać 10-znakowe sufiksy i „puszczać” je nie od q0 tylko od pewnego stanu. Resztę porządny student potrafi już sobie sam dopowiedzieć.