Zanim podamy formalna definicję automatu skończonego spróbujmy go przybliżyć.
Za automat skończony możemy przyjąć układ mający pewną liczbę np. / wejść i innąnp. k wyjść. Istotną rzeczą jest, że sygnały x występujące na wejściu należą do skończonego zbioru symboli wejściowych X. zaś sygnały wyjściowe y należą do skończonego zbioru sygnałów wyjściowych Y.
Ze względu na skończoność zbiorów symboli wejściowych i wyjściowych mówimy o automatach skończonych.
Automat taki przedstawia poniższy rysunek:
Automat posiadający tylko sygnały wejściowe i wyjściowe jest dość ubogi. W automacie tym dany zestaw sygnałów wejściowych wywoła zawsze ten sam sygnał wyjściowy. Taki automat nazywa się często układem kombinacyjnym. Jest on jednak użyteczny — służy do projektowania układów logicznych.
Bardziej skomplikowane i ciekawe to układy sekwencyjne, gdzie reakcja automatu na sygnał wejściowy zależy od "historii automatu", czyli od tego jakie sygnały odbierał automat w przeszłości. Wiedza automatu o jego "historii" zawarta jest w zbiorze stanów wewnętrznych Si.... Sp. Stany te wraz z sygnałem wejściowym Xj określają stany wyjściowe Yj.
Możemy teraz podać formalną definicję automatu skończonego.
Jest to niatka elementów:
A = (Q, T, P. q. F), gdzie:
Q — skończony i niepusty zbiór stanów,
T — alfabet służący do budowy języka (alfabet terminalny),
P — funkcja przejść — opisująca zmianę stanu (w jakim sensie analogon zbioru produkcji w gramatyce), q — wyróżniony stan początkowy, F — zbiór stanów końcowych.
Funkcja P określona jest na iloczynie kartezjańskim T x Q i przyjmuje wartość w Q czyli
F: T x O =» O
czyli w oparciu o sygnał wejściowy € T i stan wewnętrzny € Q określa nowy stan wewnętrzny € Q.