Given a regular language defined by a regular expression, we can convert it to an NFA, which is equivalent to a right-regular grammar. The grammar is not generally LL(1).
However, if we convert the NFA to a DFA, the latter is equivalent to a right-regular grammar that is LL(1). For example, according to this tool, the regex (ab|cd)*ab becomes the grammar (with start symbol A):
A -> a B | c C
B -> b D
C -> d E
D -> ɛ̝ | a B | c C
E -> a B | c C
If we minimize the DFA, it's equivalent to a more concise grammar (7 productions instead of 9):
A -> a B | c C
B -> b D
C -> d A
D -> ɛ̝ | a B | c C
However by inspection, there's a more concise LL(1) right-regular grammar for the same language, with 5 productions:
A -> a b D | c d A
D -> ɛ̝ | a b D | c d A
Or even 4 productions:
A -> a b D | c d A
D -> ɛ̝ | A
Is there an algorithm I can use to generate a minimal (i.e. with fewest productions) LL(1) right-regular grammar from a regular expression? Perhaps by inserting additional step(s) before/during/after the regex => NFA => DFA => Min-DFA conversion?
