|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Об автоматной сложности регулярных языков при выпадениях специального видадипломная работа (Бакалавр)
- Научный руководитель: Дергач П.С.
- Автор: Мамадалиева Феруза Шухратбек кизи
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2020
- Аннотация: В работе Ф. Мамадалиевой решаются две следующие задачи. В первой задаче дано произвольное слово длины n в конечном алфавите и к нему разрешается применять любое конечное число раз следующую операцию: удалить в нем две соседние буквы и написать на их месте любую букву алфавита. Эта операция в работе названа как операция выпадения-вставки типа 2-> 1. Необходимо найти автоматную сложность полученного множества слов. Вторая задача имеет то же условие, но уже для конкретной пары слов 0^n, 1^n в алфавите {0,1}. С первой задачей студентка справилась в полном объеме и привела соответствующее решение. Во второй задаче студенткой построен соответствующий автомат с правильным обоснованием, но его точное число состояний не посчитано. Найдены только совпадающие по порядку верхние и нижние оценки.
- Добавил в систему: Дергач Пётр Сергеевич