# Is there an algorithm to overapproximate a context free grammar by a regular expression?

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?

• Sure, there are many over-approximations that are tighter. For instance, figure out which letters can appear in the first position of a word in the context-free language. If it is $a,b,d$ (say), then you can have the regular expression (a|b|d).*. Your algorithm is also a possible option. There's an infinite family of better over-approximations. Without any further requirements, I'm not sure how much useful one can say here. – D.W. May 1 '19 at 10:59
• Ah, I see. Even the algorithm in my question can be made arbitrarily precise by replacing recursion only after a number of repetitions. What should I do with the question now? – rahul May 1 '19 at 13:00

One classical answer to this question is Parikh's theorem. Parikh's theorem states that the histograms of all words in a context-free language form a semilinear set. Conversely, the language of all words whose histogram belongs to a semilinear set is regular. Since the proof of Parikh's theorem is constructive, you can in principle take a context-free grammar and come up with a regular over-approximation.

Another classical answer is the Chomsky–Schützenberger theorem, which states that every context-free language can be written in the form $$h(D \cap R)$$, where $$h$$ is a homomorphism, $$D$$ is a Dyck language, and $$R$$ is a regular language. You can over-approximate your language by $$h(R)$$, which is regular. Once again, the proof is constructive, so the over-approximation is algorithmic.

Another option is to take all parse trees of your language of a given depth $$d$$, and replace all nonterminal leaves with $$\Sigma^*$$. This generalizes your approach. However, generally speaking it won't be the case that the languages $$L_d$$ produced in this way will converge to the original language, even if you only consider parse trees corresponding to leftmost derivations.

A similar option is to convert your context-free grammar to a PDA, and take the language of all words whose length-$$n$$ prefix has some corresponding partial computation. The language $$L_n$$ do converge to the original language, for trivial reasons.

Even simpler, you can take all words of length up to $$n$$ in your language, together with $$\Sigma^n\Sigma^+$$.

These methods can of course be combined. For example, starting with the Chomsky–Schützenberger theorem, you can consider more intelligent over-approximations for the Dyck language $$D$$, for example taking all parse trees of length $$d$$ corresponding to the grammar containing the rules $$S \to \epsilon$$ and $$S \to (_i S )_i S$$.

• Can you expand on what you mean by converging to the original language? Do you mean that the regular expression from the approach I outlined will not match all strings generated by the original grammar? – rahul May 1 '19 at 17:53
• I mean that the intersection of the languages $L_n$ is the original language. – Yuval Filmus May 1 '19 at 17:54