Затраты времени на создание и запуск NFA против DFA для данного регулярного выражения
Я прохожу прошлые экзамены и постоянно сталкиваюсь с вопросами, на которые я не могу найти ответ в учебниках или в Google, поэтому любая помощь будет высоко ценится.
Вопрос, с которым у меня сейчас проблемы, заключается в следующем:
Учитывая регулярное выражение (a|bb)*, выведите оценку стоимости во времени для его преобразования в соответствующий NFA и DFA. Ваш ответ должен относиться к размеру регулярного выражения.
Подобный вопрос из другого года:
Учитывая, что для приведенного выше примера вы знаете размер исходного регулярного выражения, |r| и размер входной строки |x|, объясните, как вы будете рассчитывать затраты времени на создание и запуск NFA по сравнению с созданием и выполнением эквивалентного DFA.
Полученный NFA для (a | bb) * имеет 9 состояний, в то время как DFA имеет 4. Даже зная это, я понятия не имею, как подойти к вопросу.