\(L\) to język tych słów nad alfabetem \(\{0, 1\}\), które na dziesiątej pozycji od końca ma 0.
Dowód nie wprost.
Załóżmy, że istnieje automat \(A\), który rozpoznaje \(L\) a liczba jego stanów jest mniejsza od 1024.
Weźmy wszystkie słowa postaci \(\{0,1\}^{10}\) – jest ich dokładnie 1024. Wiemy, że przynajmniej dwa słowa, \(w\) i \(v\) kończą się w tym samym stanie \(q\), z zasady szufladkowej. Istnieje takie \(k\), że \(w[k] \neq v[k]\). Teraz dopisujemy do każdego spośród \(w\), \(v\) słowo \(u = 1^{10-k}\). Ponieważ \(A\) jest deterministyczny, a \(w\) i \(v\) kończą się w identycznym stanie \(q\) to \(\hat{\delta}(q_0, wu) = \hat{\delta}(q_0, vu)\), ale \(wu\) i \(vu\) różnią się na dziesiątej pozycji od końca, więc \(\hat{\delta}(q_0, wu) \neq \hat{\delta}(q_0, vu)\). \(\Box\)
Część z was pewnie po przeczytaniu następnego zadania zacznie sie zastanawiać, czy to faktycznie 1024, jak coś zapraszam po wyjaśnienia na priv. Zarówno 1,2 zadanie dobrze rozważać łącznie z zadaniem 9 (twierdzeniem o indeksie).