Informatyka MIMUW

Do tej części zadań może podejść Czytelnik bez żadnej znajomości teorii automatów.

1. Słowa pierwotne.Słowo $w\in\Sigma^{*}$ nazywamy pierwotnym (ang. primitive),jeśli nie da się go przedstawić $w=v^{n}$, inaczej niż dla $n=1$ i $v=w$.
   1. Dowieść, że dla każdego słowa niepustego $w$, istnieje dokładnie jedno słowo pierwotne $v$, takie że $w=v^{n}$, dla pewnego $n\geq 1$.
      Liczbę $n$ nazywamy wykładnikiem słowa $w$.
   2. O słowach $wv$ i $vw$ mówimy, że są w relacji koniugacji. Dowieść, że jest to relacja równoważności.
      Dowieść, że dwa słowa będące w relacji koniugacji mają ten sam wykładnik. Jaka jest moc klasy abstrakcji relacji koniugacji dla słowa o długości $m$ i wykładniku $n$?
2. Język nawiasowy. Wykazać, że zbiór poprawnie uformowanych ciągów nawiasów może być zdefiniowany na dwa równoważne sposoby:
   
   1. Jako najmniejszy zbiór $L$ zawierający ciąg pusty oraz taki, że jeśli $w,v\in L$, to również $(w),wv\in L$.
   2. Zbiór słów nad alfabetem $\{(,)\}$, w których ilość “)” jest taka sama jak ilość “(”, a w każdym prefiksie ilość “)” jest niewiększa niż ilość “(” .
3. Zbiory semi–liniowe. Zbiór liczb naturalnych postaci $\{ a+bn\,:\, n\in{\bf N}\}$, dla ustalonych $a,b\in{\bf N}$ nazywamy liniowym. Zbiór bedący sumą skończonej liczby zbiorów liniowych nazywamy semiliniowym. (Gdy sumowana rodzina jest pusta, otrzymujemy zbiór pusty.)
   
   1. Dowieść, że każdy zbiór postaci $\{ a+b_{1}n_{1}+\ldots+b_{k}n_{k}\,:\, n_{1},\ldots,n_{k}\in{\bf N}\}$, dla ustalonych $k$ i $a,b_{1},\ldots,b_{k}\in{\bf N}$, jest semi–liniowy.
      Wskazówka. Wykorzystać podziały zbioru liczb naturalnych na klasy abstrakcji relacji przystawania modulo $m$, dla odpowiednio dobranych liczb $m$.
   2. Dowieść, że zbiór liczb naturalnych $A$ jest semi–liniowy wtedy i tylko wtedy, gdy jest prawie periodyczny tzn. gdy istnieją
      $c\in{\bf N}$ i $d\in{\bf N}-\{ 0\}$ takie, że dla każdego $x>c$, $x\in A\,\Leftrightarrow\, x+d\in A$.
   3. W grafie zorientowanym ustalamy dwa wierzchołki. Interesuje nas zbiór długości wszystkich możliwych ścieżek pomiędzy tymi wierzchołkami. Dowieść, że jest to zbiór semi–liniowy.
   4. Dowieść, że rodzina zbiorów semi–liniowych jest zamknięta na skończone sumy, przecięcia oraz na uzupełnienie względem $N$.
4. Graf gry (J. P. Jouannaud). Rozważamy następującą grę pomiędzy Barmanem i Klientem. Przed Barmanem na obrotowym talerzu stoją cztery szklanki tworząc wierzchołki kwadratu. Szklanka może być ustawiona normalnie lub dnem do góry, jednak Barman ma przepaskę na oczach i rękawiczki na rękach, tak że nie może tego zobaczyć ani wyczuć. Ruch Barmana polega na odwróceniu jednej lub dwóch dowolnie wybranych szklanek. Ruch Klienta polega na obróceniu talerza (o wielokrotność ćwierć-obrotu). Barman wygrywa, jeśli w jakimś momencie gry wszystkie szklanki ustawione są w tej samej pozycji (zostanie o tym lojalnie poinformowany).

   Czy Barman noże wygrać startując z nieznanej konfiguracji początkowej, a jeśli tak, to w jakiej liczbie ruchów?

   Czy graliby Państwo o pieniądze z Barmanem ? A gdyby zamiast kwadratu były 3 szklanki ustawione w trójkąt lub 5 w pięciokąt ?

5. Kody. Zbiór $C\subseteq\Sigma^{+}$ nazywamy kodem, jeśli każde słowo $w\in\Sigma^{*}$ dopuszcza co najwyżej jedną faktoryzację względem $C$ (tzn., da się “odkodować”).
   Niech $\Sigma=\{ a,b\}$. Dowieść, że zbiór $\{ aa,baa,ba\}$ jest kodem, a zbiór $\{ a,ab,ba\}$ nie jest.

   Jeśli skończony zbiór $C$ nie jest kodem, oszacować z góry długość najkrótszego słowa, które o tym świadczy (tzn. dopuszcza dwie różne faktoryzacje).

6. Oznaczmy: $x\preceq y$ jeśli słowo $x$ jest podciągiem $y$, np. $ab\preceq aabb$. Jest to częściowy porządek.
   Udowodnić następujący fakt znany jako Lemat Higmana.

   Jeśli $|\Sigma|<\infty$ to dla każdego $X\subseteq\Sigma^{*}$ zbiór jego słów minimalnych w sensie $\preceq$ jest skończny.

   Wskazówka. Przypuśćmy, że teza jest fałszywa. Wtedy istnieje w $\Sigma^*$ nieskończony ciąg słów $x_{1},x_{2},..$ taki że  $i < j\ \rightarrow\ not\ (x_{i}\preceq x_{j})$ (ale może być $x_{j}\preceq x_{i}$). Wybierzmy taki ”minimalny” ciąg w sensie długości, tzn. $|x_{1}|$ minimalne, jeśli $x_{1}$ ustalone to $|x_{2}|$ minimalne itd. Wybierzmy podciąg nieskończony $x_{{i_{1}}},x_{{i_{2}}}..$ wszystkich słów z tego ciągu zaczynających się na pewną taką samą literę $a$. Usuńmy tę literę z początku każdego z tych słów otrzymując ciąg $x^{{\prime}}_{{i_{1}}},x^{{\prime}}_{{i_{2}}}..$.  Wtedy ciąg $x_{1},x_{2},\ldots,x_{{i_{1}-1}},x^{{\prime}}_{{i_{1}}},x^{{\prime}}_{{i_{2}}},x^{{\prime}}_{{i_{3}}}\ldots$ spełnia te same warunki co początkowy ciąg i jest ”mniejszy”, sprzeczność.

7. Niech $sup(L)$ oznacza zbiór nadciągów słów z języka $L$. Udowodnić, że dla dowolnego $L$ nad skończonym alfabetem $sup(L)$ jest językiem regularnym.

   Wskazówka. Skorzystaj z lematu Higmana (poprzednie zadanie)..

8. Niech $subs(L)$ oznacza zbiór podciągów słów z języka $L$. Udowodnić, że dla dowolnego $L$ nad skończonym alfabetem $subs(L)$ jest językiem regularnym.

   Wskazówka. Skorzystać z poprzedniego zadania.