1. Przedstaw graf reprezentujący działanie maszyny Turinga analizującej nieskończony ciąg złożony z liter {a,b,c}. Jeżeli maszyna napotka literę 'b' zamienia ją miejscami z poprzednią literą w ciągu.

np. cbab => cabb => cbba => bbca

2. Napisz algorytm, wybierz instrukcję kluczową, oszacuj złożoność czasową algorytmu. Podaj rząd złożoności oraz dowody dla dużego O oraz omegi.

Tablica n x n, gdzie n-parzyste
(tablica w załączniku)

3. Napisz wyrażenie regularne definiujące wszystkie l. nieparzyste w kodzie dziesiętnym zawierające co najwyżej dwie czwórki.

4. Dla podanego wyrażenia regularnego narysuj automat z epsilon przejściami oraz napisz równorzędną gramatykę:

[(ABC)⁺| 010]*


5.  Dla podanej gramatyki przedstaw 3 przebiegi generacji elementów do zbioru jęz. użytych w kategoriach syntaktycznych,

<a> --> <a><b><c>
<a> --> 8
<b> --> <a> + <b>
<b> --> epsilon
<c> --> 5|7

---