Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

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

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

 


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

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




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

<== попередня сторінка | наступна сторінка ==>
Недетерміновані скінченні автомати | Основний закон електромагнетизму

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.003 сек.