Определение 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. Если и , то .
Доказательство. Лемму легко доказать индукцией по количеству тактов в вычислительном процессе, ведущем из конфигурации в конфигурацию .