A regular language R may be considered a superset approximation for a context-free language L, if L⊆R. A good approximation forL is the one for which the set R−L is as small as possible. There are considerable methods to find a regular approximation for a context-free language. The most significant consist in building, through several transformations applied to the original pushdown automaton (or context-free grammar), the most appropriate finite automaton (regular grammar) recognizing (generating) a regular superset approximation of the original context-free language. How accurate the approximation is, depends on the transformations applied to the considered devices.
However, the perfect regular superset (or subset) approximation for an arbitrary context-free language cannot be built. For surveys on approximation methods and their practical applications in computational linguistics (especially in parsing theory) the reader is referred to [155,158]. Methods to measure the accuracy of a regular approximation can be found in [43,76,194].
In the sequel we propose a new approximation technique that emerges from the Chomsky-Sch¨utzenberger theorem. In brief, the method consists in transforming the original context-free grammar into a context-free grammar in Dyck normal form. For this gram-mar we build the refined extended dependency graph G.eS described in Section 3.3.
FromG.eS we depict a state diagramAe for a finite automaton and a regular grammar
Gr= (Nr, T, Pr, S) that generates a regular (superset) approximation for L(Gk) (which is nothing else than the image throughϕof the languageRm built in Section3.3).
Let Gk = (Nk, T, Pk, S) be an arbitrary context-free grammar in Dyck normal form, and G.eS = (Ve, Ee) the extended dependency graph of Gk. Recall that Ve = {[−i |[i∈ N(1)∪Nr(2)∪N(3)} ∪ {]−j |]j ∈Nl(2)∪Nr(2)∪N(3)} ∪ {S} in which some of the vertices may be ~-marked, in order to prevent repetition of the same bracket when building the digraph associated with a plus-height regular expression. In brief, the state diagramAe can be built by skipping in G.eS all left brackets in Nr(2) and all brackets in N(3), and labeling the edges with the symbol produced by left or right bracket inN(2)∪N(1). This reasoning is applied no matter whether the vertex inVeis~-marked or not. Therefore, we avoid~-marker specifications when buildingAe, unless this is strictly necessary. Denote bysf the accepting state ofAe. Thestart stateofAeissS, whereS is the axiom ofGk.
Chapter 3. Homomorphic Representations and Regular Approximations of Languages
i sf, respectively. In both cases, this is labeled byλ. We set inPr a rule of the form ]qi →λor ]qti →λ, respectively.
The new grammarGr= (Nr, T, Pr, S), in which the set of rulesPris built as above, and Nr = {]−i |]i ∈ N(2)} ∪ {[−i ,]−i |[i,]i ∈ N(1)} is a regular grammar generating a regular superset approximation for L(Gk). Recall that some of the brackets in Nr may also be
~-marked (by distinct symbols). It is easy to observe that L(Gr) =ϕ(Rm), whereϕ is the homomorphism in the proof of Theorem 3.6.
Note that since the regular language in the Chomsky-Sch¨utzenberger theorem is an ap-proximation of the trace-language,Rm depends on the considered context-free grammar in Dyck normal form. As for L=L(Gk) there exist several other grammars generating it, setting these grammars in Dyck normal form other trace-languages can be drawn, and consequently other regular languages, of typeRm, can be built. The best approximation forL is the regular language with fewer words that are not inL.
Denote byGLthe set of grammars in Dyck normal form generatingL, byRm the set of all regular languages obtained from the refined extended dependency graphs associated with grammars in GL, and by AL={ϕ(Rm)|Rm ∈ Rm} the set of all superset regular approximations of L. It is easy to observe thatAL, with the inclusion relation on sets, is a partially ordered subset of context-free languages. AL has an infimumequal to the
context-free language it approximates, but it does not have the least element. Indeed, as proved in [22, 92, 93, 94], there is no algorithm to build for a certain context-free language L, the simplest context-free grammar that generates L. Hence, there is no possibility to identify the simplest context-free grammar in Dyck normal form that gen-eratesL. Therefore, there is no algorithm to build the minimal superset approximation forL. Where by thesimplest grammar we refer to a grammar with a minimal number of nonterminals, rules, or loops (grammatical levels encountered during derivations).
Consequently, AL does not have the least element.
It would be interesting to further study how the (refined) extended dependency graphs (see Construction3.2and Section3.3), associated with grammars in Dyck normal form generating a certain context-free language L, vary depending on the structure of these grammars10, and what makes the structure of the regular languageRm(hence the regular superset approximation) simpler. In other words, to find a hierarchy on AL depending on the structure of the grammars in Dyck normal form that generate L. These may also provide an appropriate measure to compare languages in AL. On the other hand, for an ambiguous grammar Gk, there exist several paths (hence regular expressions) in the refined extended dependency graph, which “approximate” the same word inL(Gk).
Apparently, finding an unambiguous grammar for L(Gk) may refine the language Rm. The main disadvantage is that, again in general, there is no algorithm to solve this problem. Moreover, even if it is possible to find an unambiguous grammar forL(Gk), it is doubtful that the corresponding regular language Rm is finer than the others.
In [92] it is also proved that the cost of the “simplicity” is the ambiguity. In other words, finding an unambiguous grammar for L = L(Gk) may lead to the increase in size (e.g., number of nonterminals, rules, levels, etc.) of the respective grammar. Which again, may enlargeRmwith useless words. Therefore, a challenging matter that deserves further attention is whether the unambiguity is more powerful than the “simplicity” in determining a more refined regular superset approximation for a certain context-free language (with respect to the method proposed in this section).
Example 3.4. a. The regular grammar that generates the regular superset approxima-tion of the linear context-free language in Example3.1isGr= ({S,]1,]t2,]t3,]4,]t5,]6,[t7,]t7}, {a, b, c, d}, S, Pr), where11 Pr= {S→a]1,]1→b]4,[4→ b]6,]6→ a]1/a[t7,[t7→ a]t7,]t7 → d]t5,]t5 →c]t3,]t3→ b]t2,]t2 → c]t3,]t2 → d]t5,]t2 → λ}. The language generated by Gr is L(Gr) ={(abb)maa(d(cb)n)p|n, m, p≥1}= (abb)+aa(d(cb)+)+=h(R). The transition diagram associated with the finite automaton acceptingL(Gr) is sketched in Figure3.1.
10For instance, how does the extended dependency graph associated with anonself-embeddinggrammar in Dyck normal form look, and what is the corresponding regular superset approximation.
11Note that, since there is only one dependency graph that yields only one plus-height regular expres-sion there is no need of the labeling procedure described in Section3.3.
Chapter 3. Homomorphic Representations and Regular Approximations of Languages
Figure 3.5: The transition diagram Ae built from G.eS in Example3.3. Each bracket [i
(S, ]i) inAecorresponds to the states[i (sS,s]i) (see Example3.4.b.). Sis the initial vertex, vertices colored in green lead to the final state.
b. The regular grammar that generates the regular superset approximation of the context-free language in Examples3.2and 3.3 isGr= ({S,]3t2 , ...,]7t2 ,]2t3 ,]3t3 ,]4t3 ,]6t3 ,[1t4 , ...,[7t4 ,]1t4 , ...,]7t4 ,]1t5 ,]27, ...,]77,¯]47,¯]67},{a, b, c}, S, Pr), where Pr= {S → c[1t4 ,[it4→ c]it4,]1t4 → b]1t5 ,]jt4 → a]jt3,]mt4 → b]mt2 ,]1t5 → a]27,]j7 → a]j7,]n7 → c[nt4 ,]k7 → a¯]k7,¯]k7 → c[kt4 ,]2t3 → a]37/a]67/a]77,]jt3 → a]jt3,]3t3 →a]37/a]47/a]57,]kt3 →b]kt2 ,]lt2→a]27/λ,]ht2 →b]3t2 ,]3t2 →b]3t2 /a]27/λ|i∈{1,2,3,4,5,6,7}, j∈{2,3,4,6}, h∈{4,5}, k∈{4,6}, l∈{6,7}, m∈{5,7}, n∈{2,3,5,7}}. The transition dia-gram associated with the finite automaton that acceptsL(Gr) is sketched in Figure3.5.