3813100528

słowa wejściowego nie będzie istnieć przejście maszyny ze stanu, w którym będzie się ona akurat znajdowała czytając ten symbol.

Przykład 1.7.

Rozważmy znowu maszynę A\ z Przykładu 1.3. Niech U2 = abbbbba będzie słowem wejściowym tej maszyny. Ai nie ma obliczenia na słowie U2- Istotnie, działanie maszyny zakończy się już po przeczytaniu pierwszego symbolu „6”, bowiem nie istnieje przejście maszyny A\ ze stanu Si poprzez symbol „6”.

Przykład 1.8.

Niech teraz 113 = aaabbbbaba będzie słowem wejściowym automatu A2 z Przykładu 1.3. Ciągi stanów

S0S1S1S1S2S3S3S3S4S2

oraz

so^iS2S0S0S0S0S0S1^S2

są przykładowymi obliczeniami A2 na słowie 113.

Maszyna deterministyczna wykonuje obliczenia bardzo podobnie jak jej nie-deterministyczny odpowiednik, z tą różnicą, że obliczenie maszyny deterministycznej na danym słowie zawsze istnieje i jest jedyne.

Przykład 1.9.

Rozważmy deterministyczną skończenie stanową maszynę *43 z Przykładu 1.4. Niech 114 — 01011101 będzie słowem wejściowym tej maszyny. Ciąg stanów

sosisiso^isososi

jest jedynym obliczeniem ^3 na słowie 114.

1.2. Pojęcie automatu skończonego

W tym podrozdziale przedstawimy definicje niedeterministycznego i deterministycznego automatu skończonego, wprowadzimy pojęcia akceptacji oraz języka rozpoznawanego przez automat skończony. Pokażemy też, że klasa języków rozpoznawanych przez skończone automaty deterministyczne i klasa języków rozpoznawanych przez skończone automaty niedeterministyczne pokrywają się.

11