Как конечный автомат распознаёт регулярный язык

Конечный автомат обрабатывает входную строку, переходя между состояниями из конечного множества. Детерминированные и недетерминированные конечные автоматы распознают один и тот же класс регулярных языков; отдельного неограниченного хранилища памяти у такой модели нет.