Математическая теория формальных языков
Конфигурация конечного автомата
Определение 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| и число достижимых из
(в смысле ) конфигураций?
