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

Визначення 2.2.1. Конфігурацією або миттєвим описом (instantaneous description) скінченного автомату називається довільна впорядкована пара , де и .

Визначення 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, стани q₁, q₂ і слова x, y, z, такі що і ?

Вправа 2.2.11. Як повязані |Q|, , , |w| і число досяжних з (в розумінні ) конфигурацій?