Teoria automatów i języków formalnychautor :  Maria Foryś, Wit Foryś

format :  B5
objętość :  108 str.

ISBN  83[zasłonięte]87674-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