3813100529

1.2.1. Definicja automatu skończonego

Niech E będzie alfabetem.

Definicja 1.10. Niedeterministycznym automatem skończonym (w skrócie NFA, od słów „Nondeterministic Finite Automaton”) nad alfabetem E nazywamy parę JC = (A, F), gdzie:

1.    A jest niedeterministyczną skończenie stanową maszyną,

2.    F CS.

Zgodnie z powyższą definicją niedeterministyczny automat skończony jest układem złożonym z maszyny A oraz zbioru F. Zbiór F jest tzw. zbiorem stanów końcowych (akceptujących).

Od tej pory zamiast „niedeterministyczny automat skończony” będziemy mówić „automat skończony”.

Definicja 1.11. Deterministycznym automatem skończonym (w skrócie DFA, od słów „Deterministic Finite Automaton”) nazywamy parę JC = (A, F), gdzie

1.    A jest deterministyczną skończenie stanową maszyną,

2.    FCS.

Używając oznaczeń z paragrafu 1.1.1, możemy przedstawić automaty skończone na diagramie. Aby wskazać, że dany stan jest stanem końcowym, oznaczamy go podwójnym okręgiem:

Definicja 1.12. Niech JC — (A, F) będzie automatem skończonym nad alfabetem E. Obliczeniem automatu JC na słowie u £ E* nazywamy obliczenie maszyny A na u. Podobnie obliczeniem deterministycznego automatu skończonego JC — (A, F) na u nazywamy obliczenie maszyny deterministycznej A na u.

Przedmiotem naszych rozważań będą szczególne rodzaje słów - słowa akceptowane przez automat skończony, tzn. takie, na których przeprowadza on „udane” obliczenie. Udane, czyli rozpoczynające się w stanie początkowym i kończące w stanie akceptującym.

Formalna definicja słowa akceptowanego przez JC (odpowiednio JC) jest następująca.

Definicja 1.13. Mówimy, że automat skończony JC = (A,F) nad alfabetem E akceptuje słowo

u — co&i... a_m € E*

12