Вариант 6: Даны α, буква x и натуральное число k. Вывести, есть ли в языке L слова, содержащие ровно k букв x.
Обрабатывать регулярное выражение слева направо, как при приведении в обычную запись, но в стек складывать не сами операнды, а возможные количества вхождений в них искомой буквы (в диапазоне от 0 до k включительно). Если между операндами стоит плюс, то у результата возможные значения числа букв будут получаться путем поэлементной дизъюнкции, так как можем выбрать любой из операндов. Если точка, то в результате будут все возможные суммы допустимых значений. Если звездочка, то все возможные произведения допустимых значений на натуральные числа (не превышающие k). На последнем шаге достаточно посмотреть на то, возможно ли ровно k вхождений буквы в регулярку, поскольку оно уже будет посчитано.
Внешний цикл проходит по всему регулярному выражению один раз, а обработка каждого символа работает либо за O(k) (для {+, a, b, c, 1}), либо за O(k^2) (для {., * }) . То есть в худшем случае время работы не превышает O(N * k^2).