Начало см. здесь.

Ахо А., Ульман Дж.
Теория синтаксического анализа, перевода и компиляции. Том 1.

Пер. с англ. М.: Мир 1978, c. 135.

Общее представление о конечном автомате как о некотором "распознавателе языка" можно получить здесь.

Здесь обозначение в соответствии со стандартными определениями обозначает множество всех (включая и "пустую") цепочек в алфавите (этот алфавит по приведенному ранее определению автомата интерпретируется как "множество допустимых входных символов автомата").

В приведенном определении понятия "конфигурация", есть декартово произведение множества состояний автомата и множества всех цепочек в алфавите (включая и "пустую" цепочку).

Таким образом отдельная конфигурация (в соответствии с определением понятия "декартово произведение двух множеств") будет некоторой упорядоченной парой, первый элемент которой есть некоторое состояние автомата, а второй элемент есть некоторое слово в алфавите (этот алфавит по приведенному ранее определению автомата интерпретируется как "множество допустимых входных символов автомата").

Все эти формальные определения очень понятно иллюстрируются на примере конкретного недетерминированного автомата, подробно описанного здесь.

Продолжение см. здесь.