8299308030

•    A-rachunek — czyli rachunek funkcji rekurencyjnych.

Zostanie on również pokrótce przedstawiony.

Jako podstawowy podręcznik do automatów skończonych (podrozdz. 1.2.1) i maszyn Tu-ringa (podrozdz. 1.2.2), a także do rozdziału 1.3 może służyć Hopcroft, Motwani i Ullman [10]. Głównym podręcznikiem do A-rachunku (podrozdz. 1.2.3) jest Barendregt [4].

1.2.1 Automaty skończone

W najprostszej swojej postaci automat skończony służy do definiowania języków, czyli do odróżniania słów spełniających pewne kryteria od słów ich niespełniających.

Definicja 1.1

Deterministycznym automatem skończonym (DFA¹) nazywamy piątkę A = (Q,X,8,q₀,F) w której

•    Q jest skończonym zbiorem t.zw. stanów;

•    S jest skończonym zbiorem t.zw. liter; zbiór £ jest zwykle nazywany alfabetem;

•    5:QxS—> Q to t.zw. funkcja przejścia automatu; nieformalnie mówiąc, wyznacza ona stan, do jakiego automat ma przejść z danego stanu po wczytaniu danej litery;

•    9o £ Q jest wyróżnionym stanem początkowym;

•    F C Q jest wyróżnionym zbiorem stanów końcowych lub akceptujących.

Należy zwrócić uwagę, że stan początkowy jest zawsze dokładnie jeden, podczas gdy stanów końcowych jest cały zbiór; w szczególnym (nieciekawym) przypadku może to być zbiór pusty 0, albo pełny zbiór Q.

4

1

Od ang. Deterministic Finite Automaton.