Аннотация:В работе А. Шевцовой решается следующая задача. Дана пара A,B регулярных языков в алфавите {0,1}. Говорим, что функция алфавитного кодирования f:{0,1}->{0,1}* допустима для языка, если она на нем однозначно декодируема. Нужно проверить на вложимость класс допустимых кодирований первого языка с классом допустимых кодирований второго языка.
Студентка должна была разобраться в решении этой задачи, взятом из диссертации научного руководителя, и написать реализующую соответствующий алгоритм программу. В паре с ней работала студентка магистратуры Рахматова Валерия. Распределение обязанностей между ними было следующим: Ангелина пишет программу и общую описательную часть алгоритма. Валерия пишет математическую составляющую, доказывающую корректность используемого алгоритма.
Для упрощения задачи студентке было разрешено считать, что шаги 1 и 2 уже выполнены. То есть ей уже на вход программы подается примитивный язык с полиномиальной функцией роста. Ей необходимо было выполнить шаги 3,4,5. Это было успешно реализовано в данной работе. Написана соответствующая программа.