Конфигурация конечного автомата
Определение 2.2.1. Конфигурацией или мгновенным описанием (instantaneous description) конечного автомата 
называется любая упорядоченная пара 
, где 
и 
.
Замечание 2.2.2. Содержательно конфигурация представляет собой "мгновенное описание" конечного автомата. Если представить, что исходное слово, принадлежность которого рассматриваемому языку надо проверить, дано в некотором "входном потоке", то в конфигурации слово w есть та часть исходного слова, которая пока осталась во входном потоке (это некоторый суффикс исходного слова), а q - текущее состояние "управляющего устройства".
Определение 2.2.3. Определим на множестве всех конфигураций конечного автомата M бинарное отношение 
( такт работы (step)) следующим образом. Если 
и , то 
. Иногда вместо пишут 
.
Пример 2.2.4. Рассмотрим конечный автомат
из примера 2.1.2. Тогда 
.
Определение 2.2.5. Бинарное отношение 
определяется как рефлексивное, транзитивное замыкание отношения .
Пример 2.2.6. Для конечного автомата из примера 2.1.2 выполняется 
и 
.
Лемма 2.2.7. Пусть дан конечный автомат 
. Слово принадлежит языку L(M) тогда и только тогда, когда для некоторых 
и 
верно 
.
Лемма 2.2.8. Если 
и 
, то 
.
Доказательство. Лемму легко доказать индукцией по количеству тактов в вычислительном процессе, ведущем из конфигурации 
в конфигурацию 
.
Упражнение 2.2.9. Рассмотрим конечный автомат.
Перечислить все конфигурации , удовлетворяющие условию 
.
Упражнение 2.2.10. Существуют ли конечный автомат M, состояния q1, q2 и слова x, y, z, такие что 
и 
?
Упражнение 2.2.11. Как связаны |Q|, 
, 
, |w| и число достижимых из (в смысле ) конфигураций?