3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. May 1 at 10:59
  • $\begingroup$ 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? $\endgroup$ – rahul May 1 at 13:00
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – rahul May 1 at 17:53
  • $\begingroup$ I mean that the intersection of the languages $L_n$ is the original language. $\endgroup$ – Yuval Filmus May 1 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.