Математическая теория формальных языков

       

Конфигурация конечного автомата


Определение 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| и число достижимых из

(в смысле ) конфигураций?



Содержание раздела