3813100536

Spis treści

Wstęp    2

Spis symboli i podstawowe definicje    5

1.    Automaty skończone    6

1.1.    Skończenie stanowe maszyny wykonujące obliczenia    na skończonych słowach............................. 6

1.1.1.    Pojęcie skończenie stanowej maszyny............ 7

1.1.2.    Obliczenia skończenie stanowej maszyny na skończonych

słowach............................ 9

1.2.    Pojęcie automatu skończonego ................... 11

1.2.1.    Definicja automatu skończonego .............. 12

1.2.2.    Języki rozpoznawane przez automaty skończone...... 14

1.2.3.    Równoważność automatów deterministycznych i niedeter-

ministycznych......................... 15

2.    Automat BiichPego jako przykład w-automatu    20

2.1.    Pojęcia wstępne............................ 20

2.2.    Definicja Automatu Biichi’ego.................... 24

2.3.    Języki akceptowane przez AB.................... 26

3.    Inne typy u;-automatów    30

3.1.    Automaty Mullera.......................... 30

3.2.    Automaty Rabina .......................... 32

3.3.    Automaty Streeta........................... 36

4.    Równoważność NAB, NAM, NAR    i    NAS    39

4.1.    Twierdzenie o równoważności NAB, NAM, NAR, NAS...... 40

Podsumowanie    47

Spis literatury    48

1