Teoria automatów i języków formalnych
autor : Maria Foryś, Wit Foryś
format : B5
objętość : 108 str.
ISBN 83-87674-92-3
|
Teoria automatów i języków formalnych autor : Maria Foryś, Wit Foryś format : B5 ISBN 83-87674-92-3 |
Książka jest nowoczesnym wprowadzeniem do klasycznej już dzisiaj teorii, a znajomość podstawowych jej pojęć i własności stanowi kanon wykształcenia każdego informatyka. Prezentuje ona teorię języków formalnych w zakresie hierarchii Chomsky'ego wraz z odpowiednimi klasami gramatyk i automatów. Zawiera również rozdział poświęcony rozmaitościom języków i monoidów.
Książka jest przeznaczona dla studentów kierunków informatycznych i matematycznych uniwersytetów i uczelni technicznych, a także dla pracowników naukowych zajmujących się informatyką, matematyką, automatyką i lingwistyką matematyczną.
1. Elementy teorii półgrup
1.1. Definicje i podstawowe własności
1.2. Półgrupy wolne i monoidy wolne
1.3. Podmonoidy monoidów wolnych
2. Języki i gramatyki
2.1. Klasyfikacja Chomsky'ego
3. Języki regularne
3.1. Automaty
3.2. Automat minimalny
3.3. Automat niedeterministyczny
3.4. Lemat o pompowaniu
3.5. Wyrażenia regularne
3.6. Twierdzenie Kleene
3.7. Własności języków regularnych i gramatyk regularnych
4. Rozmaitości języków, monoidów i półgrup
5. Języki bezkontekstowe
5.1. Gramatyki języków bezkontekstowych
5.2. Lemat o pompowaniu
5.3. Własności rodziny języków bezkontekstowych
5.4. Jednoznaczność języków bezkontekstowych
5.5. Języki liniowe
5.6. Równania dla języków
5.7. Automat ze stosem
6. Języki kontekstowe i języki typu (0)
6.1. Języki kontekstowe
6.2. Automat liniowo ograniczony
6.3. Maszyna Turniga i języki typu (0)
6.4. Problemy zamkniętości na działania
6.5. Problemy rozstrzygalne i nierozstrzygnalne algorytmicznie
Skorowidz