Создание набора всех возможных совпадений для заданного regex

Мне интересно, как найти набор всех совпадений для данного regex с конечным числом совпадений.

Например:

Все эти примеры можно считать начинающимися с ^ и заканчивающимися $

`hello?` -> (hell, hello)
`[1-9][0-9]{0,3}` -> (1,2,3 ..., 9998, 9999)
`My (cat|dog) is awesome!` -> (My cat is awesome!, My dog is awesome!)
`1{1,10}` -> (1,11, ..., 111111111, 1111111111)
`1*` -> //error
`1+` -> //error
`(1|11){2}` -> (1,11,111,1111) //notice how it doesn't repeat any of the possibilities

Мне также было бы интересно, есть ли способ найти count a unique a solutions to the regex или есть ли способ определить, имеет ли regex конечное число решений.

Было бы неплохо, если бы алгоритм мог разобрать любой regex, но достаточно мощное подмножество regex будет вполне подходящим.

Меня интересует решение этой проблемы на PHP, но другие языки тоже подойдут.

EDIT:

На занятиях по теории формальностей я узнал о DFA, которые могут быть использованы для реализации regex (и других регулярных языков). Если бы я мог преобразовать regex в DFA, решение показалось бы мне довольно простым, но это преобразование кажется мне довольно сложным.

EDIT 2:

Спасибо за все предложения, см. мое сообщение о публичном проекте на github, над которым я работаю, чтобы "ответить" на этот вопрос.