JFiZO - Zadanie 11.007

Ź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, 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.

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.