Further Refinements of the Regular Language in the Chomsky-Sch¨ utzenberger

One of the main disadvantage of considering ∗-height regular expressions in building the extended dependency graph associated with a context-free grammar in Dyck nor-mal form is that some ∗-loops composed of right brackets in N_r⁽²⁾∪N⁽³⁾ may not be symmetrically arranged according to their corresponding left brackets in Nr⁽²⁾∪N⁽³⁾, if we consider their corresponding core segment as a symmetrical center. This is due to the possibility of having “λ-loops”. This deficiency does not affect the intersection with a Dyck language, but it has the disadvantage of enlarging considerable the regular language in the Chomsky-Sch¨utzenberger theorem. This can be avoided by considering only loops described in terms of +-Kleene closure.

Another disfunction of the extended dependency graph built through Construction3.2is the concatenation of a regular expressionr.e^(l,X)_[t

i

with another regular expressionr.e^(r,X_[t ⁰⁾ i

, r.e^(r,X_[t ⁰⁾

i

6= r.e^(r,X)_[t

i (due to the common tie [^t_i that marks a core segment). This can be avoided by a renaming procedure of the regular expressions we want to concatenate.

All these additional modifications in building an extended dependency graph are useful only if we want to refine the regular language that satisfies the Chomsky-Sch¨utzenberger theorem (with regards to the grammar in Dyck normal form). This will be further handled (in Section3.4) to build a tighter approximation for the context-free language it characterizes.

Each regular expression of a finite star-height can be described as a finite union of regular expressions in terms of +-Kleene closure (shortly plus-height). For instance the∗-height regular expression ]₆[₂(]₇[₃)^∗]₇[^t₄ inR^]6

[^t₄ can be forked into ]₆[₂(]₇[₃)⁺]₇[^t₄ and ]₆[₂]₇[^t₄. The plus-height of a regular expression, can be defined analogous to the star-height of a regular expression in [98], as follows.

Definition 3.11. Let Σ be a finite alphabet. The plus-heighth(r) of a regular expression r is defined recursively as follows: i. h(λ) =h(∅) =h(a) = 0 for a∈Σ, ii. h(r₁∪r₂) = h(r1r2) = max{h(r₁), h(r2)}, and h(r⁺) =h(r) + 1.

Chapter 3. Homomorphic Representations and Regular Approximations of Languages Note that for any star-height regular expression it is possible to build a digraph, with an initial vertex v_i and a final vertex v_f, such that all paths in this digraph, from v_i to vf, to provide the respective regular expression (which can be done in a similar manner as in Construction3.2). However, if the regular expression is described in terms of plus-height then this statement may not be true (due to the repetition of some symbols). To force this statement be true, also for plus-height regular expressions, each repetition of a bracket is marked by a distinct symbol (e.g., ]₆[₂(]₇[₃)⁺]₇[^t₄ becomes ]₆[₂(]₇[₃)⁺¯]₇[^t₄), and then, for the new plus-height regular expression obtained in this way, we build a digraph with the above property. In order to recover the initial plus-height regular expression from the associated digraph, a homomorphism that maps all the marked brackets (by distinct symbols) into the initial one must be applied. Each time it is required, we refer to such a vertex as a~-marked vertex. Therefore, due to the technical transformations described above and the symmetrical considerations used in the construction of a trace-language, we may assume to work only with plus-height regular expressions.

LetGk = (Nk, T, Pk, S) be an arbitrary context-free grammar in Dyck normal form, and G^X the dependency graph of G_k (see Construction 3.1). Denote by P^X

[^t_i the set of all plus-height regular expressions over ˜Nk ∪ {X} that can be read in G^X, starting from the initial vertex X and ending in the final vertex [^t_i. The cardinality of P_[^Xt

i is finite.

Now, we consider the same homomorphism as defined for the case of the set R^X_[t i

i we build a new plus-height regular expression r.e^(r,X_[t ⁾

i = h^r_G(r.e^(l,X)_[t

i the set of all (plus-height) regular expressionsr.e^X_[t

i obtained as

Note that linear context-free languages do not need an extended dependency graph. The set of all regular expressions P.e^S suffices to build a regular language in the Chomsky-Sch¨utzenberger theorem (see Theorem3.10) that cannot be further adjusted by using the graphical method proposed in this section. Furthermore,|R.e^S| ≤ |P.e^S|. Equality takes place only when each regular expression inR.e^S is a plus-height regular expression (see Example3.1). For the case of context-free languages the plus-height regular expressions inP.emust be linked with each other in such a way it approximates, as much as possible, the trace-language associated with the respective context-free language.

In order to find an optimal connection of the regular expressions in P.e, we consider the following labeling procedure of elements in P.e. Denote by c0 the cardinality of P.e^S and by cj the cardinality of P.e^]j, where ]j ∈ N⁽³⁾. Each regular expression r ∈ P.e^S is labeled by a unique q, 1 ≤ q ≤ c₀, and each regular expression r ∈ P.e^]j,

is labeled by a unique q, such that Pi−1

r=0cr + 1 ≤ q ≤ Pi

r=0cr, 1 ≤ i ≤ s, and s = |{]_j|]_j ∈ N⁽³⁾}|. Denote by r^q the labeled version of r. To preserve symmetric structures that characterize trace-words of context-free languages, then when we link regular expressions in P.e between them, each bracket in a regular expression r^q is upper labeled by q. Exception makes the first bracket occurring in r^q (which is a bracket in {]_j|]j ∈ N⁽³⁾}). Now, a refined extended digraph can be built similar to that described in Construction3.2. To have a better picture of how the labeled regular expressions must be linked to each other, and where further relabeling procedures may be required (to obtain a better approximation of the trace-language), we first build for each plus-height regular expressionr^q∈ P.e^]j, ]j ∈N⁽³⁾, a digraph and then connect all these digraphs to each other. Denote by G^q,]j the digraph associated with r^q ∈ P.e^]j, such that ]_j is the initial vertex and the final vertex is the last bracket occurring in r^q. Each digraphG^q,]j read from the initial vertex ]j to the final vertex provides the regular expression r^q. Hence, any digraph G^q,]j has vertices labeled by brackets of the forms {[^q_j|[j∈ N⁽¹⁾ ∪Nr⁽²⁾ ∪N⁽³⁾} ∪ {]^q_j|]j ∈ N_l⁽²⁾ ∪Nr⁽²⁾ ∪N⁽³⁾}, c0 ≤ q ≤ Ps

r=0cr, with the exception of the initial vertex ]_j, ]_j ∈ N⁽³⁾. Some of vertices in G^q,]j, besides the q-index, may also be~-marked, in order to prevent repetitions of the same vertex which may occur in a plus-height regular expression. As the construction of the dependency graph does not depend on~-markers, unless it is necessary, we avoid~-marked notations in further explanations when building this dependency digraph.

The adjacent vertex Y to ]_j, in G^q,]j, is calledsibling. Any edge of the form ]⁻_l ]⁻_k, where ]l ∈ N⁽³⁾, ]k ∈ Nr⁽²⁾∪N⁽³⁾, is called dummy edge, while ]⁻_l (]⁻_k, if ]k ∈ N⁽³⁾, and the adjacent vertex to ]⁻_k is a right bracket in Nr⁽²⁾ ∪N⁽³⁾) is a dummy vertex. An edge that is not a dummy edge is called stable edge. Denote by G^]j the set of all digraphs G^q,]j, i.e., their initial vertex is ]j. Any digraphG^q,]j has only one vertex labeled by a bracket [^q_k, [_k∈N⁽¹⁾, which stands for a core segment in a trace-word. Right brackets ]^q_j, ]j ∈ Nr⁽²⁾ ∪N⁽³⁾, must be symmetrically arranged according to their left pairwise [^q_j, [_j∈ Nr⁽²⁾∪N⁽³⁾, that occur at the left side of [^q_k. A dummy vertex labeled by ]^q_j, ]j ∈N⁽³⁾, allows the connection with any digraph in G^]j. A digraph in G^]j with a final vertex labeled by a bracket [⁻_k, [⁻_k ∈N⁽¹⁾, or by a bracket ]⁻_l , ]_l∈Nr⁽²⁾, is calledterminal, because the vertex [⁻_k or ]⁻_l , respectively, does not allow more connections.

Next we describe the procedure that builds a refined extended digraph with the property that reading this digraph (in which each loop is a plus-loop) from the initial vertexS to all its final vertices, we obtain those (plus-height) regular expressions that form a regular language that provides a refined approximation of the corresponding trace-language.

Step 1. First we build a digraphG.e^Sthat describes all (plus-height) regular expressions in P.e^S. This can be done by connecting all digraphs in G^S to S. Since each bracket

Chapter 3. Homomorphic Representations and Regular Approximations of Languages labeling a vertex in G^q,S, 1≤q ≤c0, is uniquely labeled by q, and there exists a finite number of brackets, G.e^S is correct (in the sense that it is finite and any vertex occurs only one time). The initial vertex ofG.e^S isS. If a graph inG^S has a final vertex labeled by a bracket [^q_i, [_i∈N⁽¹⁾ or by a bracket ]^q_i, ]_i ∈Nr⁽²⁾, then this is also a final vertex in G.e^S. IfG_kis a grammar in linear-Dyck normal form thenG.e^S, built in this way, suffices to build the regular language in the Chomsky-Sch¨utzenberger theorem. The set of all paths from S to each final vertex to which we apply the homomorphismh_k, defined in the proof of Theorem3.10, yields a regular languageRmthat cannot be further adjusted, such that the Chomsky-Sch¨utzenberger theorem still holds. Therefore, R_m is minimal with respect to the grammar Gk and the Chomsky-Sch¨utzenberger theorem, i.e., the equalityϕ(D_K∩Rm) =ϕ( L(G_k)) still holds, where ϕis the homomorphism defined in the proof of Theorem 3.6.

Step 2. For each vertex ]^q_j existing inG.e^S, such that ]_j ∈N⁽³⁾, we connect all digraphs inG^]j toG.e^S. This can be done by adding to G.e^S a new edge ]^q_jY, for each sibling Y of ]_j (in G^]j). If Z is the adjacent vertex of ]^q_j (in the former version of G.e^S), i.e., ]^q_jZ is a dummy edge, then we remove inG.e^S the edge ]^q_jZ, while in G^q0,]j ∈ G^]j (connected to G.e^S through ]^q_j) we remove the vertex ]j and consequently, the edge ]jY. For the moment, all the other edges inG^q0,]j are preserved inG.e^S, too. Besides, ifV is the final vertex of G^q0,]j, then a new edgeV Z is added to G.e^S. IfV ∈ {[⁻_k|[_k∈N⁽¹⁾} ∪ {]⁻_l |]_l ∈ Nr⁽²⁾}, i.e.,G^q0,]j is a terminal digraph then the edgeV Z is aglue edge, i.e., it is a stable edge that makes the connection of G^q0,]j into G.e^S (or more precisely the connection of G^q0,]j to the digraph G^q,S in which it has been inserted). Otherwise, V Z is a dummy edge, which will be removed at a further connection with a digraph in G^V. Since for the case of linear context-free languages generated by a grammar in linear-Dyck normal form, G.e^S does not contain any dummy vertex, the construction of G.e^S is completed atStep 1.

A vertex in G.e^S labeled by a bracket ]^q_j, ]j ∈ N⁽³⁾, that has no adjacent vertex, i.e., the out degree of the vertex labeled by ]^q_j is 0, is called apop vertex. When connecting a digraph G^q0,]j toG.e^S, through a pop vertex, if G^q0,]j is a terminal digraph, then the final vertex of G^q0,]j becomes a final vertex of G.e^S. If G^q0,]j is not a terminal digraph, then the final vertex ofG^q0,]j becomes a pop vertex for G.e^S.

If there exist more than one vertex labeled by an upper indexed⁶ bracket ]^q_j^¯, ]_j ∈N⁽³⁾, then, ifG^q0,]j has been already added toG.e^S there is no need to add another “copy” of G^q0,]j. It is enough to connect ]^q_j^¯to the digraph existing inG.e^S, i.e., to add a new edge ]^¯q_jY, whereY is a sibling of ]j inG^q0,]j. This observation holds for any element inG^]j. The procedure described at Step 2 is repeated for each new dummy or pop vertex added to

6AsG.e^S is finite, there cannot exist inG.e^S two right brackets ]j, ]j∈N⁽³⁾, upper indexed by the same value.

G.e^S. For each transformation performed on G.e^S, we maintain the same notationG.e^S for the new obtained digraph. The construction ofG.e^S ends up then when each vertex ]⁻_j, ]j ∈N⁽³⁾, has been connected to a digraph in G^]j, i.e., no dummy and pop vertices exist in G.e^S. The only permissible contexts under which a bracket ]⁻_j , ]_j ∈N⁽³⁾, may occur, in the final version ofG.e^S, are of the forms ]⁻_i ]⁻_j [⁻_k, [⁻_h]⁻_j [⁻_k, ]⁻_i ]⁻_j ]⁻_l , and [⁻_h]⁻_j]⁻_l , where ]i∈Nr⁽²⁾, [_h ∈N⁽¹⁾, [_k∈N⁽¹⁾∪Nr⁽²⁾∪N⁽³⁾, ]_l∈N_l⁽²⁾.

There are several refinements that can be done on G.e^S in order to the resulted regu-lar language to better approximate the trace-language associated with the considered context-free language. Two peculiar situations may occur when adding digraphs toG.e^S: I₁. First, suppose that during the construction of G.e^S by subsequently connecting digraphs between them, starting from ]^q_j, ]j ∈N⁽³⁾, we reach a terminal digraph with a final vertex ]^q_k⁰, ]_k ∈Nr⁽²⁾, such that ]^q_k⁰ is linked toZ, forming thus a stable (glue) edge ]^q_k⁰Z. Denote by℘= ]^q_j...]^q_k⁰Z the path (inG.e^S) from ]^q_j to ]^q_k⁰Z, obtained at this stage. If the vertex preceding ]^q_k⁰ in℘is ]^q_j⁰, ]j ∈N⁽³⁾, i.e.,℘= ]^q_j...]^q_j⁰]^q_k⁰Z, then connecting ]^q_j⁰ (]^q_j⁰]^q_k⁰ is a dummy edge), through its siblings, to digraphs in G^]j another edge ]^q_k⁰]^q_k⁰ preceded by ]^q_j⁰]^q_k⁰, is added to G.e^S, i.e., ℘ becomes ℘ = ]^q_j...]^q_j⁰(]^q_k⁰)²Z. Since ]^q_j⁰]^q_k⁰ is a dummy edge, the vertex ]^q_j⁰ must be again connected to digraphs in G^]j, and so on, until ]^q_j⁰ is connected to a terminal digraph G^{q,]¯ j} ∈ G^]j, ¯q 6=q⁰, that has a final vertex labeled by a bracket ]^qm^¯, ]m ∈Nr⁽²⁾ (m and knot necessarily distinct), or by a bracket [^qm^¯, [m∈N⁽¹⁾ such that ]^¯q_m is not preceded by a bracket of the form ]⁻_j , ]_j ∈ N⁽³⁾. Then ℘ will be either of the form ]^q_j℘1]^qm^¯(]^q_k⁰)⁺Z or of the form ]^q_j℘1[^qm^¯(]^q_k⁰)⁺Z, respectively. On the other hand, sinceG^{q,]¯ j} ∈ G^]j the digraphG^{q,]¯ j} can be added toG.e^S, through ]^q_j, from the very first beginning, avoiding thus the plus-loop (]^q_k⁰)⁺, i.e., there should exist in G.e^S a new path℘⁰ = ]^q_j℘₂]^qm^¯Z or℘⁰= ]^q_j℘₂[^qm^¯Z (where ℘₂ is a path inG^{q,]¯ j}). This allows two other new paths to be created in G.e^S, i.e., ¯℘ = ]^q_j℘₂]^¯q_m(]^q_k⁰)⁺Z (or ℘⁰⁰ = ]^q_j℘₂[^q_m^¯(]^q_k⁰)⁺Z) and

¯

℘⁰ = ]^q_j℘1]^qm^¯Z(or ¯℘⁰⁰= ]^q_j℘1[^qm^¯Z), which are of no use in approximating the trace-language (hence in building the regular language in the Chomsky-Sch¨utzenberger theorem). Paths

¯

℘and ¯℘⁰ (℘⁰⁰, ¯℘⁰⁰) do not affect the intersection with the Dyck language but they enlarge the regular language with useless words. In order to avoid the paths ¯℘and ¯℘⁰ (or℘⁰⁰, ¯℘⁰⁰) the terminal digraphG^{q,]¯ j} receives a new label ˜q, besides of label ¯q (which is maintained to allow ℘ to be produced). To allow the shorter path ℘⁰ to be created, instead of G^{q,]¯ j} the terminal digraph G^{q,]˜ j} is connected to G.e^S through the dummy vertex ]^q_j. Hence ℘⁰ becomes ℘⁰ = ]^q_j...]^qm^˜Z (or ℘⁰ = ]^q_j...[^qm^˜Z), while ℘ remains ]^q_j...]^qm^¯(]^q_k⁰)⁺Z (or ]^q_j...[^qm^¯(]^q_k⁰)⁺Z, respectively). This relabeling procedure is used for any case similar to that described above⁷ encountered during the computation ofG.e^S. As there may exist a

7For instance, ]^q_k⁰ may also be a dummy vertex and ]^q_k⁰Z a dummy edge.

Chapter 3. Homomorphic Representations and Regular Approximations of Languages finite number⁸of plus-loops inG.e^S, there will be a finite number of “relabeled” digraphs (not necessarily terminal). A loop (not necessarily a self-loop) may be reached through different paths that must be “renamed” (if we want to avoid that loop).

I₂. Another situation that requires a relabeling procedure may occur when connecting a digraph to G.e^S through a pop vertex. Suppose that ]^q_j, ]j ∈ N⁽³⁾, is a pop vertex, and the digraphG^q0,]j that must be added toG.e^S has been already connected through a dummy vertex labeled by ]^¯q_j (i.e.,G^q0,]j has been already inserted inG.e^S). According to the procedure described atStep 2 the vertex ]^q_j is linked to the sibling of ]j inG^q0,]j already existing inG.e^S. Since the connection ofG^q0,]j toG.e^S has been done through a dummy vertex, the final vertex inG^q0,]j cannot be neither a final vertex inG.e^S (ifG^q0,]j is a terminal digraph) nor a pop vertex.

To forbid a pop vertex ]⁻_j to overlap with a dummy vertex ]⁻_j, each of the digraphs connected to G.e^S through a pop vertex, is renamed by a new label. Denote by ¯G^]j the labeled version ofG^]j. Then connections through pop vertices will be done by using only digraphs in ¯G^]j. However, any dummy vertex ]⁻_j , that is not a pop vertex, obtained by connecting digraphs in ¯G^]j toG.e^S should be connected to the original digraphs inG^]j, unless a relabeling procedure described atI₁ is required.

Denote by ¯N_k = {[⁻_i |[_i∈ N⁽¹⁾ ∪Nr⁽²⁾∪N⁽³⁾} ∪ {]⁻_j |]_j ∈ N_l⁽²⁾∪Nr⁽²⁾∪N⁽³⁾}, the set of vertices composing G.e^S, in which some brackets may be ~-marked (by distinct ~-markers). To reach the regular language in the Chomsky-Sch¨utzenberger theorem we denote byRG the set of all regular expressions obtained by readingG.e^S from the initial vertexSto any final vertex. First, suppose thatG_kdoes not have an extended grammar.

We have K = k and D_k⁰ = L(G_k). Consider the homomorphism h_k: ¯N_k ∪ {S} → {[_i,]i|[_i,]i∈Nr⁽²⁾∪N⁽³⁾}∪{[_i]i|[_i,]i∈N_l⁽²⁾∪N⁽¹⁾}∪{λ}, defined byhk(S) =λ,hk([⁻_i ) = [i, h_k(]⁻_i ) = ]_i, for any ]_i ∈ Nr⁽²⁾, h_k(]⁻_i ) = [_i]_i, for any ]_i ∈ N_l⁽²⁾, and h_k([⁻_i ) = [_i]_i, for any [i∈ N⁽¹⁾. Then Rm = hk(RG) is a regular language with Dk ∩Rm = L(Gk).

Furthermore,R_m is a strength refinement ofR, such that the Chomsky-Sch¨utzenberger theorem still holds. This is because when building regular expressions inP.eeachr.e^(l,X)_[t

i

is linked only to its right pairwiser.e^(r,X)_[t i

(due to plus-height considerations and labeling procedures). In this way all plus-loops in r.e^(l,X)_[t

i are correctly mirrored (through h^r_G) into its correct pairwiser.e^(r,X)_[t

i

. The case ofλ-loops is taken by the relabeling procedure described at I₁. This is also applicable each time we want to fork a path in G.e^S in order to avoid useless loops on that path. The relabeling procedure I₂ allows to leave G.e^S without re-loading another useless path. That is why the regular language Rm

built this way is a tighter approximation of L(G_k). A finer language thanR_m can be

8The plus-height of a regular expression obtained from any digraph in G^]j is finite related to the length of the strings inL(Gk).

Figure 3.3: a. - e. Graphs associated with regular expressions inP.e(Example3.2). Initial vertices are colored in red, final vertices are colored in blue, while purple vertices mark a core

segment. ¯]⁴₇ is a marked vertex to allow the plus-loop ([⁴3]⁴7)⁺.

found by searching for a more efficient grammar in Dyck normal form, with respect to the number of rules and nonterminals.

If G_k has an extended grammar G_k+p = (N_k+p, T, P_k+p, S) (built as in the proof of Theorem 3.6) then RG is augmented with ∇_e ={S[_tk+1, ..., S[_tk+p} and h_k is extended to h_K, h_K: ¯N_k ∪ {S} ∪ {[_tk+1, ...,[t_k+p} → {[_i,]i|([_i,]i) ∈ Nr⁽²⁾∪N⁽³⁾} ∪ {[_i]i|([_i,]i) ∈ N_l⁽²⁾∪N⁽¹⁾} ∪ {[_tk+1]_tk+1, ...,[_tk+p]_tk+p} ∪ {λ}, h_K(x) = h_k(x), x /∈ {[_tk+1, ...,[_tk+p}, and hK([tk+j) = [tk+j]tk+j, 1≤j≤p,K=k+p.

Example 3.3. Consider the context-free grammar in Example 3.2with the dependen-cy graphs drawn in Figure3.2. The setP.eof labeled plus-loop regular expressions, built from these dependency graphs, is composed ofS([¹₁)⁺[¹₅[^1t₄ ]^1t₅(]¹₁)⁺ (which corresponds to G^1,S in Figure 3.3.a), ]1[²₆([²₃]²₇)⁺[^2t₄(]^2t₃ )⁺]²₆ (with the associated digraph G^2,]1 in Fig-ure 3.3.b), ]₆[³₂[³₆([³₃]³₇)⁺[^3t₄(]^3t₃ )⁺]³₆]^3t₂ (with the associated digraph G^3,]6 in Figure 3.3.c), ]6[⁴₂(]⁴₇[⁴₃)⁺]⁴₇[^4t₄ (]^4t₃)⁺]^4t₂ or the ~-marked version ]6[⁴₂(]⁴₇[⁴₃)⁺¯]⁴₇[^4t₄ (]^4t₃)⁺]^4t₂ (with the associ-ated digraphG^4,]6 in Figure 3.3.d), and ]₆[⁵₂]⁵₇[^5t₄ ]^t5₂ (with the associated digraph G^5,]6 in Figure 3.3.e).

The extended dependency graph built with respect to the refinement procedure is sketched in Figure3.4. The terminal digraphsG^6,]6 andG^7,]6 are introduced with respect to the relabeling procedure I₁, in order to prevent the loop yielded by the ”iterated“

digraph G^3,]6 to occur between G^2,]1 and G^6,]6 (or G^7,]6). It also forbids the self-loop (]^3t₂ )⁺to be linked to G^6,]6 (or toG^7,]6), then when the digraphG^3,]6 is not added to the corresponding path. Due to the self-loop (]¹₁)⁺, in which ]¹₁ is a pop vertex, we did not applied the relabeling procedure described atI₂ (applying it leads to the same result).

Chapter 3. Homomorphic Representations and Regular Approximations of Languages

Figure 3.4: The refined dependency graph of the context-free grammar in Example 3.2 and Example3.3. S is the initial vertex, vertices colored in green are final vertices, vertices colored in blue are dummy vertices, vertices colored in purple mark a core segment. Orange edges emphasize symetrical structures built with respect to the structure of the trace-language.

Green edges are glue edges.

3.4 On a Regular Superset Approximation for