|
[ Pobierz całość w formacie PDF ]
J¸zyki, automaty, zlozonosc obliczeniowa Joanna J¸drzejowicz Andrzej Szepietowski 23 pazdziernika 2007 Przedmowa Podrecznik niniejszy jest przeznaczony dla studentów drugiego roku kierunku informatyki i zawiera materiał wykładu z lingwistyki matematycznej, prowadzonego przez autorów na Uniwersytecie Gdanskim i na Politechnice Gdanskiej. Chcemy serdecznie podziekowac słuchaczom naszych kursów za cenne uwagi i zywe reakcje. Myslimy, ze pomogły nam one napisac lepszy podrecznik. Głównym celem wykładu jest zapoznanie słuchaczy z teoretycznymi podstawami in- formatyki. Chcemy wyjasnic co to jest algorytm, oraz przekazac intuicje na temat tego, co jest a co nie jest obliczalne, co ma łatwe rozwi azanie algorytmiczne a co jest trudne. Podrecznik zawiera podstawowe wiadomosci z lingwistyki matematycznej, teorii ob- liczalnosci oraz teorii złozonosci obliczeniowej. Zawiera wiele przykładów, zadan oraz zagadnien do samodzielnego rozwi azania. Nie wymaga sie od czytelnika specjalnego przygotowania, poza znajomosci a mate- matyki na poziomie szkoły sredniej oraz pewnych podstawowych umiejetnosci programi- stycznych. Gdansk, 7 maja 2007 autorzy 4 Spis tresci Przedmowa 3 1 Alfabety, słowa, jezyki 9 1.1 Jezyki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Operacje na jezykach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Klasa REG jezyków regularnych 15 Wyrazenia regularne 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Automat skonczony (deterministyczny) . . . . . . . . . . . . . . . . . . 19 2.3 Automat niedeterministyczny . . . . . . . . . . . . . . . . . . . . . . . . 27 Determinizacja automatu skonczonego . . . . . . . . . . . . . . . . . . . 2.4 30 2.5 Automaty z przejsciami . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.6 Twierdzenia Kleene’ego . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.7 Iloczyn kartezjanski dwóch pełnych automatów . . . . . . . . . . . . . . 43 2.8 Operacje na jezykach regularnych . . . . . . . . . . . . . . . . . . . . . 45 2.9 Operacja podstawienia . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.10 Jezyki nieregularne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.11 Twierdzenie Myhilla-Nerode’a . . . . . . . . . . . . . . . . . . . . . . . 51 2.12 Automat dwukierunkowy . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.13 Wyrazenia regularne w narzedziach programistycznych . . . . . . . . . . 58 2.14 Zagadnienia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.14.1 Operacja przeplotu . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.14.2 Skonczone jezyki regularne . . . . . . . . . . . . . . . . . . . . 61 Zagniezdzenie -Kleene’ego w wyrazeniu regularnym 2.14.3 . . . . . . 62 2.14.4 Automat minimalny . . . . . . . . . . . . . . . . . . . . . . . . 62 Funkcje rozrózniaj ace 2.14.5 . . . . . . . . . . . . . . . . . . . . . . . 63 Tozsamosci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.14.6 63 5 [ Pobierz całość w formacie PDF ] |
Podobne
|