Reputation: 187
What is the Standard Algorithm to convert any given Regular Expression(RE) to a Left (or Right) Linear Grammar?
I know I can do this like this (to write Linear Grammar from RE):
RegEx -> NFA -> DFA -> Right Linear grammar
.
For a direct approach, I can handle simple regex like (0 + 10)*
and create a linear grammar.
But when there is, say, a nested kleene star, its really hard to produce a CFG that is linear, without any well-defined method.
I saw some answers to similar questions here and here. But they do not provide a general algo or does not convert the regex to a linear grammar.
In particular, how do I convert this : (((01+10)*00)*11)*
directly to a linear grammar, using some algorithm?
Any help is appreciated.
EDIT
Did some more searching. And got this.
Constructing an Equivalent Regular Grammar from a Regular Expression
Upvotes: 4
Views: 3721
Reputation: 187
Constructing an Equivalent Regular Grammar from a Regular Expression
Upvotes: 1