Jajo

Od lat prowadzę ćwiczenia z przedmiotu Języki, Automaty i Obliczenia, w skrócie JAiO, zwanego potocznie „jajo”.

Ma on swój standardowy zbiór zadań, a w nim następujące pytanie-zadanie:

Zadanie. Czy istnieje taki nieregularny język $\text{[math]}$ że $\text{[math]}$ jest językiem regularnym?

Ma się rozumieć, odpowiedź należy uzasadnić.

Długo by opowiadać, co to są języki, w tym języki regularne, co oznacza mnożenie języków (a tak naprawdę konkatenacja). Oczywiście, nie mogę tego wyjaśnić, bo wówczas Redakcja na pewno nie przyjęłaby mi tego artykułu do numeru pod hasłem „Jakie to proste”.

Jeśli jednak studenci nie wymyślą wystarczająco szybko jakiegoś innego rozwiązania, zaczynam udzielać im podpowiedzi. Tak się miło składa, że po kilku takich podpowiedziach zadanie w sam raz nadaje się do pokazania tutaj.

Wygląda ono wtedy tak:

Zadanie. Czy istnieje zbiór $\text{[math]}$ liczb naturalnych, który sam nie jest prawie-okresowy, ale zbiór $\text{[math]}$ jest prawie-okresowy?

Zbiór $\text{[math]}$ jest okresowy, gdy dla pewnego $\text{[math]}$ i każdej liczby naturalnej $\text{[math]}$ mamy $\text{[math]}$ Łatwo sobie taki zbiór wyobrazić: informacja o tym, które liczby naturalne z przedziału $\text{[math]}$ należą do $\text{[math]}$ determinuje go całkowicie, bo dalej ten sam szablon należy/nie należy powtarza się w nieskończoność – trochę jakby był namalowany na osi przez malarza, który ma wzorzysty wałek do malowania o obwodzie długości $\text{[math]}$ Zbiór jest prawie-okresowy jeśli można go otrzymać ze zbioru okresowego przez dodanie lub usunięcie skończenie wielu elementów.

Teraz można już bardzo łatwo udowodnić, że taki zbiór $\text{[math]}$ istnieje.

Zacznijmy od $\text{[math]}$ Ten zbiór na pewno nie jest prawie-okresowy, bo odstępy pomiędzy jego kolejnymi elementami coraz bardziej rosną, a w zbiorze prawie-okresowym tak nie ma prawa być.

Przyjrzyjmy się teraz $\text{[math]}$

Niewątpliwie $\text{[math]}$ jest prawie-okresowy albo nie jest prawie-okresowy, ale sprawdzenie, która konkretnie z tych możliwości zachodzi, wymagałoby chyba trochę pracy. Na szczęście możemy się obyć bez tego.

W pierwszym przypadku, gdy $\text{[math]}$ jest prawie-okresowy, żądanym przykładem jest zbiór $\text{[math]}$

W drugim przypadku żądanym przykładem jest zbiór $\text{[math]}$ (wówczas nie jest on prawie-okresowy). Zastanówmy się, dlaczego zbiór $\text{[math]}$ na pewno jest prawie-okresowy.

Otóż $\text{[math]}$ Teraz przypominamy sobie twierdzenie Lagrange’a, mówiące, że

Twierdzenie. każda liczba naturalna jest sumą czterech kwadratów liczb naturalnych.

A zatem zdefiniowany w skomplikowany sposób zbiór $\text{[math]}$ to po prostu $\text{[math]}$ a ten jest oczywiście prawie-okresowy, a nawet okresowy.