• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

Визначення 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| і число досяжних з (в розумінні ) конфигурацій?

Читайте також:

1. Конфігурація Apache, додавання і налаштування модулів
2. Конфігурація АТС .ЄС-11. ємністю від 235 до 1175(12002) номерів.
3. КОНФІГУРАЦІЯ ЕОМ
4. Конфігурація і БД.
5. Конфігурація офісної АТС
6. Конфігурація ЦАТС .ЄС-11. ємністю від 1200 до 13500 номерів
7. Типова конфігурація “Бухгалтерський облік для України”.

Переглядів: 756