SPIS TREŚCI
Spis treści:
Przedmowa 7
Wykaz oznaczeń 9
1 Półgrupy i monoidy 13
2 Wolne półgrupy i monoidy 19
3 Systemy przepisujące 23
4 Języki i wyrażenia regularne 31
5 Automaty skończone 35
6 Automat minimalny, niedeterministyczny, z p-przejściami 43
7 Lemat o pompowaniu, twierdzenie Kleene'ego 59
8 Automaty skończone a wyrażenia regularne 63
9 Gramatyki bezkontekstowe i ich postaci normalne 65
10 Lemat o pompowaniu dla języków bezkontekstowych. Algorytm Cocke'a-Youngera-Kasamiego 75
11 Automat ze stosem 81
12 Równania i układy równań na słowach 87
13 Automaty liniowo ograniczone i maszyny Turinga 91
14 Rozwiązania wybranych zadań 97
14.1 Odpowiedzi do rozdziału 1 . . . . . . . . . . . . . . . . . 97
14.2 Odpowiedzi do rozdziału 2 . . . . . . . . . . . . . . . . . 100
14.3 Odpowiedzi do rozdziału 3 . . . . . . . . . . . . . . . . . 104
14.4 Odpowiedzi do rozdziału 4 . . . . . . . . . . . . . . . . . 108
14.5 Odpowiedzi do rozdziału 5 . . . . . . . . . . . . . . . . . 109
14.6 Odpowiedzi do rozdziału 6 . . . . . . . . . . . . . . . . . 115
14.7 Odpowiedzi do rozdziału 7 . . . . . . . . . . . . . . . . . 122
14.8 Odpowiedzi do rozdziału 8 . . . . . . . . . . . . . . . . . 126
14.9 Odpowiedzi do rozdziału 9 . . . . . . . . . . . . . . . . . 132
14.10 Odpowiedzi do rozdziału 10 . . . . . . . . . . . . . . . . . 137
14.11 Odpowiedzi do rozdziału 11 . . . . . . . . . . . . . . . . . 139
14.12 Odpowiedzi do rozdziału 12 . . . . . . . . . . . . . . . . . 143
14.13 Odpowiedzi do rozdziału 13 . . . . . . . . . . . . . . . . . 145
Bibliografia 147