====== JFiZO - Zadanie 11.007 ======
FIXME Źle odczytałem definicję, więc to rozwiązanie prawdopodobnie nie działa.

Pokazać, że DFA rozpoznający $Lustro(L)$ może potrzebować wykładniczo więcej stanów niż DFA rozpoznający $L$.

Niech $L$ = $L_{(0+1)^90(0+1)^*}$ będzie językiem słów nad $\{0,1\}$ mających 0 na dziesiątej pozycji.

Każdy potrafi narysować DFA o 12 stanach, który go rozpoznaje (wczytałem 0, 1, ..., 8, 9 znaków; wczytałem 10. i był on zerem; nie był zerem).

Język $Lustro(L)$ jest może nieco bardziej skomplikowany i nie chce nam się pisać dla niego regexpu, ale wiemy, że każde słowo w nim musi mieć zero na dziesiątej pozycji od końca. Oh wait, [[jfizo:zadanie09.001|zad. 1]] mówi nam, że DFA rozpoznający taki język potrzebuje 1024 stanów.

A jeszcze do tego musi zapewne sprawdzać nadal zero na początku. Tak czy siak, mamy $1024=(2-\epsilon)^{12}$ stanów. Można to uogólnić do dowolnego $k$.

TODO No faktycznie, jest źle. Ale można troszeczkę poprawić i będzie lepiej: rozważmy język $L_{2(0+1)^90(0+1)^*}$. Wtedy w $Lustro(L)$ znajdują się między innymi wyrazy opisywane przez $(0+1)^*0(0+1)^92$, których jest co najmniej 512. Załóżmy nie wprost, że DFA rozpoznający ten język (całe lustro) ma mniej niż 512 stanów, wtedy dla dwóch wyrazów osiąga ten sam stan, etc. etc.