Алгоритм перевірки пустоти мови, яка відповідає заданим специфікаціям лінійно темпоральної логіки й акцептується автоматами Бюхі, методом пошуку в глибину
Тип публікації :
Магістерська робота
Дата випуску :
2021
Автор(и) :
Гальченко Максим
eKNUTSHIR URL :
Цитування :
[APA 7] Гальченко, М. (2021). Алгоритм перевірки пустоти мови, яка відповідає заданим специфікаціям лінійно темпоральної логіки й акцептується автоматами Бюхі, методом пошуку в глибину [Магістерська робота, Київський національний університет імені Тараса Шевченка]. eKNUTSHIR. https://ir.library.knu.ua/handle/123456789/2847
[ДСТУ] Гальченко М. Алгоритм перевірки пустоти мови, яка відповідає заданим специфікаціям лінійно темпоральної логіки й акцептується автоматами Бюхі, методом пошуку в глибину : кваліфікаційна робота магістра : 12 Інформаційні технології. Київ, 2021. 64 с. URL: https://ir.library.knu.ua/handle/123456789/2847 (дата звернення: 25.07.2026).
В ходi виконання квалiфiкацiйної роботи було дослiджено складнiсть перевiрки пустоти мови автоматiв Бюхi за допомогою DFS алгоритмiв. Розглянута доцiльнiсть використання цiєї роботи в алгоритмах верифiкацiї автоматiв. Впродовж виконання квалiфiкацiйної роботи було проведено аналiз iснуючих алгоритмiв перевiрки пустоти, а саме алгоритми Nested та Two-stack. Дослiджено автоматичний пiдхiд до верифiкацiї моделей систем заданих LTL формулами.
Розроблено кросплатформний консольний продукт на основi технологiй C++ з використанням тiльки стандартної бiблiотеки шаблонiв (STL), призначений для перевiрки мови автоматiв на пустоту. Врахована можливiсть використання узагальнених автоматiв та їх перетворення для подальшого використання. Запропоновано алгоритм генерацiї довiльних автоматiв А.3. Виконано порiвняння ефективностi алгоритмiв на довiльних вхiдних даних.
Розроблено кросплатформний консольний продукт на основi технологiй C++ з використанням тiльки стандартної бiблiотеки шаблонiв (STL), призначений для перевiрки мови автоматiв на пустоту. Врахована можливiсть використання узагальнених автоматiв та їх перетворення для подальшого використання. Запропоновано алгоритм генерацiї довiльних автоматiв А.3. Виконано порiвняння ефективностi алгоритмiв на довiльних вхiдних даних.
Галузі знань та спеціальності :
12 Інформаційні технології
121 Інженерія програмного забезпечення
Файл(и) :![Ескіз]()
Вантажиться...
Формат :
Adobe PDF
Розмір :
1.99 MB
Контрольна сума :
(MD5):a09386574104f927034d39b3bfd30e14
Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution-NonCommercial 4.0 International