I understand that a context-free grammar is strictly powerful than a regular expression in that a context free grammar can represent any regular language, but not all context free languages can be represented by a regular expression. However, an over-approximation of context-free languages is possible with regular expressions. For example,
.* over approximates all context-free languages.
My question is, does there exist a more tighter approximation of a context free language by a regular expression? In particular, given a context free grammar, can I turn it into an (over-approximate) regular expression?
One option I can think of is to
- Start with the start symbol, and produce a regular expression from its alternates by joining each alternate with
- Replace any tokens in the alternate with its regular expression representation as above.
- Replace any recursion (direct or indirect) with
Has there been any research in this regard?