patternMinor
Is there an algorithm to overapproximate a context free grammar by a regular expression?
Viewed 0 times
expressionfreeregularoverapproximatealgorithmgrammarcontextthere
Problem
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,
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
Has there been any research in this regard?
.* 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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#108811, answer score: 3
Revisions (0)
No revisions yet.