====== 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.

{{tag>[listy_zadan]}}