Książka "Teoria automatów i języków formalnych" 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ą.

Spis treści:

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

Podobne książki: