automat abstrakcyjny,
mat. teoret. model urządzenia działającego samoczynnie, mającego zdolność przyjmowania sygnałów z otoczenia, zmieniania swoich stanów wewn. i wysyłania sygnałów do otoczenia;
automat abstrakcyjny
Encyklopedia PWN
istnieje kilka sformułowań automatów abstrakcyjnych, dobieranych w zależności od rodzaju problemu, którego rozwiązywaniu ma on służyć. Jednym z poglądowych przedstawień automatu abstrakcyjnego jest nieograniczona taśma z głowicą czytającą i zapisującą symbole z pewnego alfabetu w komórkach taśmy, wraz z urządzeniem sterującym, zaopatrzonym w skończony zbiór reguł (program) działania maszyny oraz pojedynczą komórkę (rejestr) mieszczącą symbol aktualnego stanu wewnętrznego. Jeżeli w rejestrze jest symbol s, a głowica wskazuje komórkę taśmy z symbolem x, to maszyna „jest w sytuacji 〈s, x〉”. Reguły mają postać dyrektyw: „jeżeli maszyna jest w sytuacji 〈s, x〉, to zmień ją na 〈t, y〉 i zmień położenie głowicy o jedną komórkę w lewo, prawo lub pozostaw ją w tym samym położeniu”.
Automat abstrakcyjny można zatem traktować jako urządzenie przekształcające ciągi symboli zapisane na taśmie; po zakończeniu działania, jeżeli ono nastąpi, zapisane na taśmie słowo ulega przekształceniu na nowe słowo. Automat abstrakcyjny reprezentuje więc („oblicza”) funkcję o argumentach i wynikach będących słowami — określoną na słowach, dla których kończy działanie. W przypadku, gdy jest to funkcja dwuwartościowa, przyjmująca jedną wartość dla słów z pewnego zbioru J, i drugą — dla słów spoza J, to taki automat nazywa się akceptorem zbioru J. Zbiór J jest pewnym językiem formalnym, stąd związek teorii automatu abstrakcyjnego z teorią języków formalnych i zastosowanie w budowie translatorów.
Nakładając ograniczenia na ruch głowicy, otrzymuje się różne klasy automatów abstrakcyjnych; im bardziej ten ruch jest ograniczony, tym mniejsza jest zdolność obliczeniowa danego automatu abstrakcyjnego, tym węższą klasę funkcji on reprezentuje. Klasy automatów abstrakcyjnych: maszyny Turinga (najogólniejsze automaty abstrakcyjne, bez ograniczeń na ruch głowicy), automaty liniowo ograniczone, automaty ze stosem oraz automaty skończone. Na tym podziale N. Chomsky (1962) oparł klasyfikację języków formalnych, znajdując odpowiednie postaci gramatyk formalnych dla klas języków akceptowanych przez automaty abstrakcyjne z wymienonych klas. Elegancką teorię algebraiczną mają automaty abstrakcyjne skończone, zdefiniowane pierwotnie nieco inaczej niż powyżej, tzn. nie jako szczególne maszyny Turinga (aczkolwiek równoważnie); pojęcia i metody tej teorii stosuje się m.in. przy budowie edytorów tekstu, układów sterowania urządzeniami przemysłowymi, w elektronice, modelowaniu układu nerwowego.
