1. Alfabet={a,b,c}. Narysować graf maszyny Turinga taki, że gdy w nieskończonym ciągu napotkamy na litera 'a' to następuje zamiana miejsc z następną komórką:

np.
      abac     

        ||
        V

      baca


2. Napisać algorytm, wskazać funkcje dominującą, policzyć złożoność i udowodnić ze nalezą do złożoności wielkie O lub omega (coś mogłem pochrzanić z tymi złożonościami)

Jest tablica nxn, n jest nieparzyste. Algorytm ma zliczać wartości z komórek jak na rysunku(czerwone pole) bez komórek leżacych na przekątnej.






3. Napisać wyrażanie regularne składające się z dowolnych cyfr definiujące dowolną liczbę parzystą, w której co najmniej raz występuje cyfra 5.



4. Narysować graf (ten z epsilon przejściami) dla wyrażania regularnego:

(AB|01)+  |  (0C1)*


5.Narysować w tabelce 3 przebiegi dla gramatyki:

<a>   ->   <b> * <c>
<a>   ->   4
<b>   ->   <a><c>
<b>   ->   1|2
<c>   ->    3