{'fraction_non_alphanumeric': 0.053557737260402055, 'fraction_numerical': 0.009668069191210845, 'mean_word_length': 3.705737416402675, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Around Context-Free Grammars - a Normal Form, a Representation Theorem, and a Regular Approximation

We introduce a normal form for context-free grammars, called Dyck normal form. This is a syntactical restriction of the Chomsky normal form, in which the two nonterminals occurring on the right-hand side of a rule are paired nonterminals. This pairwise property allows to define a homomorphism from Dyck words to words generated by a grammar in Dyck normal form. We prove that for each context-free language L, there exist an integer K and a homomorphism h such that L=h(D'_K), where D'_K is a subset of the one-sided Dyck language over K letters. Through a transition-like diagram for a context-free grammar in Dyck normal form, we effectively build a regular language R that satisfies the Chomsky-Schutzenberger theorem. Using graphical approaches we refine R such that the Chomsky-Schutzenberger theorem still holds. Based on this readjustment we sketch a transition diagram for a regular grammar that generates a regular superset approximation for the initial context-free language.


Introduction
A normal form for context-free grammars consists of restrictions imposed on the structure of grammar's productions. These restrictions concern the number of terminals and nonterminals allowed on the right-hand sides of the rules, or on the manner in which terminals and nonterminals are arranged into the rules. Normal forms turned out to be useful tools in studying syntactical properties of context-free grammars, in parsing theory, structural and descriptional complexity, inference and learning theory. Various normal forms for contextfree grammars have been study so far, but the most important remain the Chomsky normal form [17], Greibach normal form [12], and operator normal form [17]. For definitions, results, and surveys on normal forms the reader is referred to [5], [17], and [20]. A normal form is correct if it preserves the language generated by the original grammar. This condition is called the weak equivalence, i.e., a normal form preserves the language but may lose important syntactical or semantical properties of the original grammar. The more syntactical, semantical, or ambiguity properties a normal form preserves, the stronger it is. It is well known that the Chomsky normal form is a strong normal form. This paper is partly devoted to a new normal form for context-free grammars, called Dyck normal form. The Dyck normal form is a syntactical restriction of the Chomsky normal form, in which the two nonterminals occurring on the right-hand side of a rule are paired nonterminals, in the sense that each left (right) nonterminal of a pair has a unique right (left) pairwise. This pairwise property imposed on the structure of the right-hand side of each rule induces a nested structure on the derivation tree of each word generated by a grammar in Dyck normal form. More precisely, each derivation tree of a word generated by a grammar in Dyck normal form, that is read in the depth-first search order is a Dyck word, hence the name of the normal form. Furthermore, there exists always a homomorphism between the derivation tree of a word generated by a grammar in Chomsky normal form and its equivalent in Dyck normal form. In other words the Chomsky and Dyck normal forms are strongly equivalent. This property, along with several other terminal rewriting conditions imposed to a grammar in Dyck normal form, enable us to define a homomorphism from Dyck words to words generated by a grammar in Dyck normal form. We have been inspired to develop this normal form by the general theory of Dyck words and Dyck languages, that turned out to play a crucial role in the description and characterization of context-free languages [9], [10], and [19]. The definition and several properties of grammars in Dyck normal form are presented in Section 1.
For each context-free grammar G in Dyck normal form we define, in Section 2, the trace language associated with derivations in G, which is the set of all derivation trees of G read in the depth-first search order, starting from the grammar axiom. By exploiting the Dyck normal form, and several characterizations of Dyck languages presented in [19], we give a new characterization of context-free languages in terms of Dyck languages. We prove (also in Section 2) that for each context-free language L, generated by a grammar G in Dyck normal form, there exist an integer K and a homomorphism ϕ such that L = ϕ(D K ), where D K (a subset of the Dyck language over K letters) equals, with very little exceptions, the trace language associated with G.
In Section 3 we show that the representation theorem in Section 2 emerges, through a transition-like diagram for context-free grammars in Dyck normal form, to the Chomsky-Schützenberger theorem. By improving this transition diagram, in Section 4 we refine the regular language provided by the Chomsky-Schützenberger theorem, while in Section 5 we show that the refined graphical representation of derivations in a context-free grammar in Dyck normal form, used in the previous sections, provides a framework for a regular grammar that generates a regular superset approximation for the initial context-free language.
The method used throughout this paper is graph-constructive, in the sense that it supplies a graphical interpretation of the Chomsky-Schützenberger theorem, and consequently it shows how to graphically build a regular language (as minimal as possible) that satisfies this theorem. Even if we reach the same famous Chomsky-Schützenberger theorem, the method used to approach it is different from the other methods known in the literature. In brief, the method in [17] is based on pushdown approaches, while that in [11] uses some kind of imaginary brackets that simulate the work of a pushdown store, when deriving a context-free language. The method presented in [1] uses equations on languages and algebraical approaches to derive several types of Dyck language generators for context-free languages. In all these works, the Dyck language is somehow hidden behind the deriva-tive structure of the context-free language (supplementary brackets are needed to derive a Dyck language generator for a context-free language). The Dyck language provided in this paper is merely found through a pairwise-renaming procedure of the nonterminals in the original context-free grammar. Hence, it lies inside the context-free grammar it describes. Each method used in the literature to prove the Chomsky-Schützenberger theorem provides its own regular language. Our aim is to find a thiner regular language that satisfies the Chomsky-Schützenberger theorem (with respect to the method hereby used) and approaching this language to build a regular superset approximation for context-free languages (likely to be as thiner as possible).
Note that the concept of a thiner (minimal) regular language, for the Chomsky-Schützenberger theorem and for the regular superset approximation is relative, in the sense that it depends on the structure of the grammar in Dyck normal form used to generate the original context-free language. In [2], [14], [15], and [16] it is proved that there is no algorithm that builds, for an arbitrary context-free language L, the minimal context-free grammar that generates L, where the minimality of a context-free grammar is considered, in principal, with respect to descriptional measures such as number of nonterminals, rules, and loops (i.e., grammatical levels [14], encountered during derivations in a context-free grammar). Consequently, there is no algorithm to build a minimal regular superset approximation for an arbitrary context-free language. Attempts to find optimal regular superset (subsets) approximations for context-free languages can be found in [4], [6], [21], and [23]. In Sections 3, 4, and 5 we also illustrate, through several examples, the manner in which the regular languages provided by the Chomsky-Schützenberger theorem and by the regular approximation can be built, with regards to the method proposed in this paper.

Dyck Normal Form
We assume the reader to be familiar with the basic notions of formal language theory [17]. For an alphabet X, X * denotes the free monoid generated by X. By |x| a we denote the number of occurrences of the letter a in the string x ∈ X * , while |x| is the length of x ∈ V * . We denote by λ the empty string. If X is a finite set, then |X| is the cardinality of X. Definition 1.1. A context-free grammar 1 G = (N, T, P, S) is said to be in Dyck normal form if it satisfies the following conditions: Note that the reasons for which we introduce the restrictions at items 2 − 4, are the following. The condition at item 2 allows to make a partition between those nonterminals rewritten by nonterminals, and those nonterminals rewritten by terminals (with the exception of the axiom). This enables, in Section 2, to define a homomorphism from Dyck words to words generated by a grammar in Dyck normal form. Conditions at items 3 and 4 allow to split the set of nonterminals into pairwise nonterminals, and thus to introduce bracketed pairs. The next theorem proves that the Dyck normal form is correct. Proof. Suppose that G is a context-free grammar in Chomsky normal form. Otherwise, using the algorithm described in [20] we can convert G into Chomsky normal form. To convert G from Chomsky normal form into Dyck normal form we proceed as follows.
Step 1 We check whether P contains two (or more) rules of the form without removing the initial rules. We call this procedure an A b -terminal substitution of A. For each rule A→ a, a ∈ T , we check whether a rule of the form A→ B 1 B 2 , B 1 , B 2 ∈ N , exists in P . If it does, then a new nonterminal A a is introduced and an A a -terminal substitution of A for the rule A → a is performed.
Step 2 Suppose there exist two (or more) rules of the form X → AB and X → B A. If we have agreed on preserving only the left occurrences of A on the right-hand sides, then according to condition 3 of Definition 1.1, we have to remove all right occurrences of A. To do so we introduce a new nonterminal Z A and all right occurrences of A, preceded at the left side by Z, in the right-hand side of a rule, are substituted by Z A. For each rule that rewrites A, A → Y , Y ∈ N 2 ∪ T , we add a new rule of the form Z A→ Y , preserving the rule A → Y . We call this procedure an Z A-nonterminal substitution of A. According to this procedure, for the rule X → B A, we introduce a new nonterminal B A, we add the rule X → B B A, and remove the rule X → B A. For each rule that rewrites A, of the Step 3 Finally, for each two rules X → AB, is introduced to replace B from the second rule, and we perform an A B(B A )-nonterminal substitution of B, i.e., we add X → A A B, and remove X → A B. For each rule that rewrites B, of the form B → Y , Y ∈ N 2 ∪ T , we add a new rule A B → Y , preserving B → Y . In the case that A occurs on the right-hand side of another rule, such that A matches at the right side with another nonterminal different of A B, then the procedure described above is repeated for A , too.
Note that, if one of the conditions 2, 3, and 4 in Definition 1.1, has been settled, we do not have to resolve it once again in further steps of the procedure. The new grammar G built as described at steps 1, 2, and 3 has the set of nonterminals N and the set of productions P composed of all nonterminals from N and productions from P , plus/minus all nonterminals and productions, respectively introduced/removed according to the substitutions performed during the above steps. Next we prove that grammars G = (N, T, P, S) in Chomsky normal form, and G = (N , T, P , S) in Dyck normal form, generate the same language. Consider the homomorphism h d : X -substitution of X, terminal or not, in the above construction of the grammar G .
To prove that L(G ) ⊆ L(G) we extend h d to a homomorphism from (N ∪ T ) * to (N ∪ T ) * defined on the classical concatenation operation. It is straightforward to prove by induction, that for each α ⇒ * . This implies that for any derivation of a word w ∈ L(G ), i.e., To prove that L(G) ⊆ L(G ) we make use of the CYK (Cocke-Younger-Kasami) algorithm as described in [20]. Let w = a 1 a 2 ...a n be an arbitrary word in L(G), and V ij , i ≤ j, i, j ∈ {1, ..., n}, be the triangular matrix of size n × n built with the CYK algorithm. Since w ∈ L(G), we have S ∈ V 1n . We prove that w ∈ L(G ), i.e., S ∈ V 1n , where V ij , i ≤ j, i, j ∈ {1, ..., n} forms the triangular matrix obtained by applying the CYK algorithm to w according to G productions.
The second relation is defined asĥ ¬t (S) = S,ĥ ¬t (X) = {X} ∪ {X |X is a (transitive) X -nonterminal substitution of X} andĥ ¬t (X) = X, if there is no substitution of X and no rule of the form X → t, t ∈ T , in G.
2}, x ∈ {t, ¬t}. Usingĥ t , each rule X→ t in P has a corresponding set of rules {X → t|X ∈ĥ t (X), X→ t ∈ P } in P . Each rule A→ BC in P has a corresponding set of rules {A → B C |A ∈ĥ ¬t (A), B ∈ĥ ¬t (B) ∪ h t (B), C ∈ĥ ¬t (C) ∪ĥ t (C), B and C are pairwise nonterminals, A → BC ∈ P } in P .
Consider V ii =ĥ t (V ii ) and V ij =ĥ ¬t (V ij ), i < j, i, j ∈ {1, ..., n}. We claim that V ij , i, j ∈ {1, ..., n}, i ≤ j, defines the triangular matrix obtained by applying CYK algorithm to rules that derive w in G . First, observe that for , B and C are pairwise nonterminals, A → BC ∈ P }. Let us explicitly develop the last union.
, B and C are pairwise nonterminals, A → BC ∈ P }. We now compute the first set of the above union, i.e., , B and C are pairwise nonterminals, A → BC ∈ P }. By the same reasoning as before, the .., n}, i.e., V ij , i ≤ j, contains the nonterminals of the n × n triangular matrix computed by applying the CYK algorithm to rules that derive w in G . Because w ∈ L(G), we have S ∈ V 1n . That is equivalent with S ∈ V 1n =ĥ t (V 1n ), if n = 1, and S ∈ V 1n =ĥ ¬t (V 1n ), if n > 1, i.e., w ∈ L(G ). Corollary 1.3. Let G be a context-free grammar in Dyck normal form. Any terminal derivation in G producing a word of length n, n ≥ 1, takes 2n − 1 steps.
Proof. If G is a context-free grammar in Dyck normal form, then it is also in Chomsky normal form, and all properties of the latter hold. Proof. Consider the homomorphism h d : The claim is a direct consequence of the way in which the new nonterminals A t , Z A, and A Z have been chosen.
Note that, due to the pairwise-renaming procedure used to reach the Dyck normal form, it may appear that a context-free grammar in Dyck normal form is more ambiguous than the original grammar in Chomsky normal form. However, this is relative. The derivation trees of a certain word have the same structure in both grammars, in Chomsky normal form and Dyck normal form (only some "labels" of the nodes in these trees differ). The apparent ambiguity can be resolved through the homomorphism h d considered in Corollary 1.4.
Let G be a grammar in Dyck normal form. To emphasis the pairwise brackets occurring on the right-hand side of a rule, and also to make the connection with the Dyck language, each pair (A, B), such that there exists a rule of the form X → AB, is replaced by an indexed pair of brackets [ i , ] i . In each rule that rewrites A and B, we replace A by [ i , and B by ] i , respectively. Next we present an example of the conversion procedure described in the proof of Theorem 1.2 along with the homomorphism considered in Corollary 1.4.
To convert G into Dyck normal form, with respect to Definition 1.1, item 2, we first remove E → a and T → a. Then, according to item 3, we remove the right occurrence of T from the rule E 1 → E 2 T , along with other transformations that may be required after completing these procedures. Let E 3 and T 3 be two new nonterminals. We remove E → a and T → a, and add the rules Let T be the new nonterminal that replaces the right occurrence of T . We add the rules E 1 → E 2 T , T → T T 1 , T → T 3 T 1 , and remove E 1 → E 2 T . We repeat the procedure with T 3 (added in the previous step), i.e., we introduce a new nonterminal T 4 , remove E 1 → E 2 T 3 , add E 1 → E 2 T 4 and T 4 → a.
Due to the new nonterminals E 3 , T 3 , T 4 , item 4 does not hold. To have accomplished this condition, we introduce three new nonterminals E 4 to replace E 2 in E 1 → E 2 T 4 , E 5 to replace E 1 in E 0 → E 3 E 1 and E → E 3 E 1 , and T 5 to replace T 1 in E 0 → T 3 T 1 and E → T 3 T 1 . We remove all the above rules and add the new rules The Dyck normal form of G , in bracketed notation, is G = ( , ] 7 }, {+, * , a}, E 0 , P ), The string w = a * a * a + a is a word in L(G ) = L(G) generated, for instance, by a leftmost derivation D in G as follows.
Applying h d to D, in G , we obtain a derivation of w in G . If we consider T the derivation tree of w in G, and T the derivation tree of w in G , then T is the homomorphic image of T through h d .

Characterizations of Context-Free Languages by Dyck Languages
The trace-word of w associated with the derivation D, denoted as t w,D , is defined as the concatenation of nonterminals consecutively rewritten in D, excluding the axiom. The trace-language associated with G k , denoted by L(G k ), is L(G k ) = {t w,D | for any w ∈ L(G k ), and any leftmost derivation D of w}.
Note that t w,D , w ∈ L(G), can also be read from the derivation tree in the depthfirst search order starting with the root, but ignoring the root and the leaves. The traceword associated with w and the leftmost derivation D in Example 2.5 is t a * a * a+a, Let G k = (N k , T, P k , S) be a context-free grammar in Dyck normal form. To emphasize possible relations between the structure of trace-words in L(G k ) and the structure of words in the Dyck language, and also to keep control of each bracketed pair occurring on the right-hand side of each rule in G k , we fix [19] we have adopted the next characterizations of D k , k ≥ 1, (Definition 2.3, and Lemmas 2.4 and 2.5). Definition 2.3. For a string w, let w i:j be its substring starting at the i th position and ending at the j th position. Let h be a homomorphism defined as follows: has an equal number of [ 1 's and ] 1 's and, in any prefix of h(w i:j ), the number of [ 1 's is greater than or equal to the number of ] 1 's.
Consider the homomorphisms defined as follows (where λ is the empty string) Lemma 2.5. We have w ∈ D k , k ≥ 2, if and only if the following conditions hold: i) (1, |w|) is a matched pair, and ii) for all matched pairs (i, j), h k (w i:j ) are in D 1 , where k ≥ 1.
is a matched pair, and either j = i + 1, or (i + 1, j − 1) is a matched pair. Definition 2.7. Let w ∈ D k and (i, j) be a matched pair of w. We say that (i, j) is reducible if there exists an integer j , i < j < j, such that (i, j ) and (j + 1, j) are matched pairs.
is a nested pair of w then (i + 1, j − 1) may be a reducible pair.
Theorem 2.8. The trace-language associated with a context-free grammar, ., ] k } be the set of nonterminals, w ∈ L(G), and D a leftmost derivation of w. We show that any subtree of the derivation tree, read in the depth-first search order, by ignoring the root and the terminal nodes, corresponds to a matched pair in t w,D . In particular, (1, |t w,D |) will be a matched pair. Denote by t w,D i:j the substring of t w,D starting at the i th position and ending at the j th position of t w,D . We show that for all matched pairs (i, j), h k (t w,D i:j ) belong to D 1 , 1 ≤ k ≤ k. We prove these claims by induction on the height of subtrees.
Basis. Certainly, any subtree of height n = 1, read in the depth-first search order, looks like [ i ] i , 1 ≤ i ≤ k. Therefore, it satisfies the above conditions.
Induction step. Assume that the claim is true for all subtrees of height , < n, and we prove it for = n. Each subtree of height n can have one of the following structures. The level 0 of the subtree is marked by a left or right bracket. This bracket will not be considered when we read the subtree. Denote by [ m the left son of the root. Then the right son is labeled by ] m . They are the roots of a left and right subtree, for which at least one has the height n − 1.
Suppose that both subtrees have the height 1 ≤ ≤ n − 1. By the induction hypothesis, let us further suppose that the left subtree corresponds to the matched pair (i l , j l ), and the right subtree corresponds to the matched pair (i r , j r ), i r = j l +2, because the position j l +1 is taken by ] m . As h is a homomorphism, we have h(t w,D i l −1: . Therefore, h(t w,D i l −1:jr ) satisfies all conditions in Definition 2.3, and thus (i l − 1, j r ) that corresponds to the considered subtree of height n, is a matched pair. By the induction hypothesis, h k (t w,D i l :j l ) and h k (t w,D ir:jr ) are in We refer to this structure as the left embedded subtree, i.e., (i l − 1, j l + 1) is a nested pair. A similar reasoning is applied for the case when one of the subtrees has the height 0. Analogously, it can be shown that the initial tree corresponds to the matched pair (1, |t w,D |), i.e., the first condition of Lemma 2.5 holds. So far, we have proved that each subtree of the derivation tree, and also each left embedded subtree, corresponds to a matched pair (i, j) and (i l , j l ), such that h k (t w,D i:j ) and h k ([ m t w,D i l :j l ] m ), 1 ≤ k ≤ k, are in D 1 .
Next we show that all matched pairs from t w,D correspond only to subtrees, or left embedded subtrees, from the derivation tree. To derive a contradiction, let us suppose that there exists a matched pair (i, j) in t w,D , that does not correspond to any subtree, or left embedded subtree, of the derivation tree read in the depth-first search order. We show that this leads to a contradiction.
Since (i, j) does not correspond to any subtree, or left embedded subtree, there exist two adjacent subtrees θ 1 (a left embedded subtree) and θ 2 (a right subtree) such that (i, j) is composed of two adjacent "subparts" of θ 1 and θ 2 . In terms of matched pairs, if θ 1 corresponds to the matched pair (i 1 , j 1 ) and θ 2 corresponds to the matched pair (i 2 , j 2 ), such that i 2 = j 1 + 2, then there exists a suffix s i 1 −1:j 1 +1 of t w,D i 1 −1:j 1 +1 , and a prefix p i 2 :j 2 of t w,D i 2 :j 2 , such that t w,D i:j = s i 1 −1:j 1 +1 p i 2 :j 2 . Furthermore, without loss of generality, we assume that (i 1 , j 1 ) and (i 2 , j 2 ) are nested pairs. Otherwise, the matched pair (i, j) can be "narrowed" until θ 1 and θ 2 are characterized by two nested pairs. If (i 1 , j 1 ) is a nested pair, then so is (i 1 − 1, j 1 + 1). As Hence, the only possibility for s i 1 −1:j 1 +1 to be, in the same time, a suffix for t w,D i 1 −1:j 1 +1 and a prefix for t w,D i:j , is the equality between the number of [ 1 's and ] 1 's in h(s i 1 −1:j 1 +1 ). This property holds if and only if s i 1 −1:j 1 +1 corresponds to a matched pair in t w,D i 1 −1:j 1 +1 , i.e., if i s and j s are the start and the end positions of where j s = j 1 + 1. We have reached a contradiction, i.e., (i 1 − 1, j 1 + 1) is reducible.
Therefore, the matched pairs in t w,D correspond to subtrees, or left embedded subtrees, in the derivation tree. For these matched pairs we have already proved that they satisfy Lemma 2.5. Accordingly, t w,D ∈ D k , and consequently the trace-language associated with G is a subset of D k . Theorem 2.9. Given a context-free grammar G there exist an integer K, a homomorphism ϕ, and a subset D K of the Dyck language D K , such that L(G) = ϕ(D K ).
Proof. Let G be a context-free grammar and G k = (N k , T, P k , S) be the Dyck normal form of In the sequel, grammar G k+p is called the extended grammar of G k . G k has an extended grammar if and only if G k (or G) has rules of the form S → t, t ∈ T ∪ {λ}. If G k does not have an extended grammar then D K = D k = L(G k ).

On the Chomsky-Schützenberger Theorem
Let G k = (N k , T, P k , S) be an arbitrary context-free grammar in Dyck normal form, with ., ] k }. and ϕ: (N k − {S}) * → T * the restriction of the homomorphism ϕ in the proof of Theorem 2.9. We divide N k into three main sets N (1) , N (2) , N (3) as follows: 1 Proof. Each linear grammar G, in standard form, is composed of rules of the forms X → λ, Transforming G into Chomsky normal form, and then into the Dyck normal form, we obtain a grammar G k in linear-Dyck normal form. Since the standard form for linear languages, Chomsky normal form, and Dyck normal form are weakly equivalent we obtain L(G) = L(G k ). The converse statement is trivial.
Next we consider more closely the structures of the derivation trees associated with words generated by linear and context-free grammars in linear-Dyck normal form and Dyck normal form, respectively. We are interested on the structure of the trace-words associated with words generated by these grammars.
Let G k = (N k , T, P k , S) be an arbitrary (linear) context-free grammar in (linear-)Dyck normal form, and L(G k ) the language generated by this grammar. Let w ∈ L(G k ), D a leftmost derivation of w, and t w,D the trace-word of w associated with D. From the structure of the derivation tree, read in the depth-first search order, it is easy to observe that each bracket [ i , such that [ i , ] i ∈ N (1) , is immediately followed, in t w,D by its pairwise ] i . The same property holds for those pairs [ t j , ] t j ∈ N (1) , such that [ t j → a nt and ] t j → a nt+1 . Using the homomorphism ϕ in Theorem 2.9, we have ϕ([ t j ) = a nt and ϕ(] t j ) = a nt+1 . For the position n t already "marked", there is no other position in w with the above property. We call [ t j ] t j the core segment of the trace-word t w,D . Trace-words of words generated by context-free grammars in Dyck normal form have more than one core segment. Each core segment induces in a trace-word (both for linear and context-free languages) a symmetrical distribution of right brackets in N (2) r ∪N (3) (always placed at the right side of the core segment) according to left brackets in N (2) r ∪N (3) (always placed at the left side of the respective core). The structure of the trace-word of a word w ∈ L(G k ), for a grammar G k in linear-Dyck normal form, is depicted in (1), where by vertical lines we emphasize the image through the homomorphism ϕ of each bracket occurring in t w,D .
.. a n−k n t −1 ...−k 1 +1 ...a n−k 2 −k 1 +1 ... a n−k 1 +1 ... a n Next our aim is to find a connection between Theorem 2.9 and the Chomsky-Schützenberger theorem. More precisely we want to compute, from the structure of trace-words, the regular and the Dyck languages yielded by the Chomsky-Schützenberger theorem. Therefore, we build a transition-like diagram for context-free grammars in Dyck normal form. First we build some directed graphs as follows.
Construction 3.3. Let G k = (N k , T, P k , S) be an arbitrary context-free grammar in Dyck normal form. A dependency graph of G k is a directed graph l } and the set of edges is built as follows. For each rule The vertex labeled by X is called the initial vertex of G X . Any vertex labeled by a left bracket in N (1) is a final vertex.
Let G X be a dependency graph of G k . Consider the set of all possible paths in G X starting from the initial vertex to a final vertex. Such a path is called terminal path. A loop or cycle in a graph is a path from v to v composed of distinct vertices. If from v to v there is no other vertex, then the loop is a self-loop. The cycle rank of a graph is a measure of the loop complexity formally defined 6 and studied in [3] and [7]. In [7] it is proved that from each two vertices u and v belonging to a digraph of cycle rank k, there exists a regular expression of star-height 7 at most k that describes the set of paths from u to v. On the other hand, the cycle rank of a digraph with n vertices is upper bounded by n log n [13]. Hence any regular expression obtained from a digraph with n vertices has the star-height at most n log n. Consequently, the (infinite) set of paths from an initial vertex to a final vertex in G X , can be divided into a finite number of classes of terminal paths. Paths belonging to the same class are characterized by the same regular expression, in terms of * and + Kleene operations, of star-height at most |V X | log |V X | (which is finite related to the lengths of strings in L(G k )).
Denote by R X , if there exists a regular expression in R.e having a substring of the 6 In brief, the rank of a cycle C is 1 if there exists v ∈ C such that C − v is not a cycle. Recursively, the rank of a cycle C is k if there exists v ∈ C such that C − v contain a cycle of rank k − 1 and all the other cycles in C − v have the rank at most k − 1. 7 Informally, this is the (maximal) power of a nested * -loop occurring in the description of a regular expression. For the formal definition the reader is referred to [7] and [18] (see also Definition 4.1, Section 4). 8 Since regular languages are closed under homomorphism and reverse operation, r.e such that there exist a regular expression in R.e with a substring of the form ] k ] j , a regular expression in R.e ] k that ends in ] k 1 , a regular expression in R.e ] k 1 that ends in ] k 2 , and so on, until a regular expression in R.e ] k m−1 ending in ] km and a regular expression in R.e ] km ending in ] i are reached.    (3) , such that there exist a regular expression in R.e S that ends in ] k , and a regular expression in R.e ] k that ends in ] i .
iii. there exists [ k , ] k ∈ N (3) such that there exist a regular expression in R.e S that ends in ] k , and [ k 1 , ] k 1 , ..., [ km , ] km ∈ N (3) such that there exist a regular expression in R.e ] k ending in ] k 1 , a regular expression in R.e ] k 1 ending in ] k 2 , and so on, until a regular expression in R.e ] k m−1 ending in ] km and a regular expression in R.e ] km ending in ] i are reached.
Denote by R e the set of all regular expressions obtained by reading all paths in G e from the initial vertex S to all final vertices (i.e., all terminal paths). We have Theorem 3.5. (Chomsky-Schützenberger theorem) For each context-free language L there exist an integer K, a regular set R, and a homomorphism h, such that L = h(D K ∩ R). Furthermore, if G is the context-free grammar that generates L, G k the Dyck normal form of G, and G k has no extended grammar, then K = k and D K ∩ R = L(G k ). Otherwise, there exists p > 0 such that K = k + p, and D K ∩ R = D K , where D K is the subset of D K computed as in Theorem 2.9.
Proof. Let G k = (N k , T, P k , S) be the Dyck normal form of G such that L = L(G). Suppose that G k does not have an extended grammar. Let h k : To prove the last equality, notice that each terminal path in a dependency graph G X (Construction 3.3) provides a string equal to a substring (or a prefix if X = S) of a traceword in L(G k ) (in which left brackets in N (2) l are omitted) generated (in the leftmost derivation order) from the derivation time when X is rewritten, up to the moment when the very first left bracket of a pair in N (1) is rewritten. This string corresponds to a regular expression r.e , which is extended with another regular expression r.e   insertions matches the number of left brackets [ j placed at the left side of the relative core (this is assured by the intersection with D k ). In fact, the extended dependency graph of G k has been conceived such that it reproduces, on regular expressions in R e , the structure of trace-words in L(G k ). The main problem is the "star-height synchronizations" for brackets in N (2) r ∪ N (3) , i.e., the number of left-brackets occurring in a loop placed at the left-side of a core segment [ t i ] t i , to be equal to the number of their pairwise right-brackets occurring in the corresponding "mirror" loop placed at the right-side of its relative core, (1) . This is controlled by the intersection of h k (R e ) with D k , leading to L(G k ). In few words, the proof is by the construction described in Construction 3.4. Another problem that occurs is that the construction of G e allows to concatenate r.e to its right pairwise r.e ) where X and X are not necessarily distinct. This does not change the intersection with the Dyck language, but enlarges the regular language R = h k (R e ) with useless 9 words.
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 2.9, then R e is augmented with ∇ e = {S[ t k+1 , ..., S[ t k+p } and h k is extended to The homomorphism h is equal to ϕ in Theorem 2.9, i.e., ϕ : Note that, for the case of linear languages there is only one dependency graph G S . The regular language in the Chomsky-Schützenberger theorem can be built without the use of the extended dependency graph. It suffices to consider only the regular expressions in If G k has an extended grammar G K , then L(G k ) = ϕ(D K ∩ h K (R.e S ∪ ∇ e )), where K = k + p, G K , ∇ e , and ϕ are defined as in Theorems 2.9 and 3.5. If G k has no extended grammar then L(G k ) = ϕ(D k ∩ h k (R.e S )). However, a graphical representation may be considered an interesting common framework for both, linear and context-free languages. Below we illustrate the manner in which the regular language in the Chomsky-Schützenberger theorem can be computed for linear (Examples 3.6) and contextfree (Example 3.7) languages.
The dependency graph G S and extended dependency graph G e of G are depicted in Figure 1.a and 1.b, respectively. There exists only one regular expression readable from G S , i.e., r.e

The regular language provided by the Chomsky-Schützenberger theorem is
→ a} The sets of regular expressions and extended regular expressions obtained by reading G S (Figure 2 respectively. The regular expressions and extended regular expressions readable from G ] 1 (Figure 2 respectively. The regular expressions and extended regular expressions obtained by reading G ] 6 (Figure 2 The extended dependency graph of G is sketched in Figure 2.d. Edges in black, are built from the regular expressions in R X [ t 4 , X ∈ {S, ] 1 , ] 6 }. Orange edges emphasize symmetrical structures, built with respect to the structure of trace-words in L(G). Some of them (e.g., ] t 2 ] 1 and ] t 2 ] t 2 ) connect regular expressions in R e between them with respect to the structure of trace-words in L(G) (see Construction 3.4, item 8). The edge ] t 2 ] 1 is added because there exists at least one regular expression in R e that contains ] 1 ] 1 (e.g. . The regular language provided by the Chomsky-Schützenberger theorem is the homomorphic image, through h k (defined in Theorem 3.5), of all regular expressions associated with all paths in the extended dependency graph in Figure 2.d, reachable from the initial vertex S to the final vertex labeled by ] t 2 , i.e., terminal paths. The interpretation that emerges from the graphical method described in this paper is that the regular language in the Chomsky-Schützenberger theorem intersected with a (certain) Dyck language lists all derivation trees (read in the depth-first search order) associated with words in a context-free grammar, in Dyck normal form or in Chomsky normal form (since these derivation trees are equal, up to an homomorphism). The intersection forms (with very little exceptions) the trace-language associated with the respective context-free grammar.
In the next section we refine the extended dependency graph G e to provide a thiner regular language in the Chomsky-Schützenberger theorem with respect to the structure of the context-free grammar in Dyck normal form obtained through the algorithm described in the proof of Theorem 1.2. Based on this readjustment in Section 5 we sketch a transition diagram for a finite automaton and a regular grammar that generates a regular superset approximation for the initial context-free language.

Further Refinements of the Regular Language in the Chomsky-Schützenberger Theorem
One of the main disadvantage of considering * -height regular expressions in building the extended dependency graph associated with a context-free grammar in Dyck normal form is that some * -loops composed of right brackets in N (2) r ∪ N (3) may not be symmetrically arranged according to their corresponding left brackets in N (2) r ∪ N (3) , 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ützenberger theorem. This can be avoided by considering only loops described in terms of + Kleene closure.
Another disfunction of the extended dependency graph built through Construction 3.4 is the concatenation of a regular expression r.e (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ützenberger theorem (with regards to the grammar in Dyck normal form). This will be further handled (in Section 5) 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 ] 6 The plus-height of a regular expression, can be defined analogous to the star-height of a regular expression in [18], as follows. 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 v f , to provide the respective regular expression (which can be done in a similar manner as in Construction 3.4). 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., ] 6 , 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.
Let G k = (N k , T, P k , S) be an arbitrary context-free grammar in Dyck normal form, and G X the dependency graph of G k (see Construction 3.3). Denote by P X l . For any element r.e Note that linear 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ützenberger theorem (see Theorem 3.5) 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 for the case when each regular expression in R.e S is a plus-height regular expression (see Example 3.6). For the case of context-free languages the plus-height regular expressions in P.e must be linked with each other in such a way it approximates, as much as possible, the tracelanguage 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 c 0 the cardinality of P.e S , i.e., |P.e S | = c 0 , and by c j the cardinality of P.e ] j , where [ j , ] j ∈ N (3) . Each regular expression r ∈ P.e S is labeled by a unique q, 1 ≤ q ≤ c 0 , and each regular expression r ∈ P.e ] j , is labeled by a unique q, such that i−1 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 , ] j ∈ N (3) }). Now, a refined extended digraph can be built similar to that described in Construction 3.4. that reading this digraph (in which each loop is a plus-loop) from the initial vertex (which is S) to all its final vertices, we obtain those (plus-height) regular expressions that form a regular language that provides the best approximation of the corresponding trace-language.
Step 1. First we build a digraph G.e S that 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 labeling a vertex in G q,S , 1 ≤ q ≤ c 0 , 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 of G.e S is S. If a graph in G S has a final vertex labeled by a bracket [ q i , r , then this is also a final vertex in G.e S . If G k is a grammar in linear-Dyck normal form then G.e S , built in this way, suffices to build the regular language in the Chomsky-Schützenberger theorem. The set of all paths from S to each final vertex to which we apply the homomorphism h k , defined in the proof of Theorem 3.5, yields a regular language R m that cannot be further adjusted, such that the Chomsky-Schützenberger theorem still holds. Therefore, we call the R m language, as minimal with respect to the grammar G k and the Chomsky-Schützenberger theorem, i.e., the equality ϕ(D K ∩ R m ) = ϕ( L(G k )) still holds, where ϕ is the homomorphism defined in the proof of Theorem 2.9.
Step 2. For each vertex ] q j existing in G.e S , such that ] j ∈ N (3) , we connect all digraphs in G ] j to G.e S . This can be done by adding to G.e S a new edge ] q j Y , 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 j Z is a dummy edge, then we remove in G.e S the edge ] q j Z, while in G q ,] j (connected to G.e S through ] q j ) we remove the vertex ] j and consequently, the edge ] j Y . For the moment, all the other edges in G q ,] j are preserved in G.e S , too. Besides, if V is the final vertex of G q ,] j , then a new edge V Z is added to G.e S .
r }, i.e., G q ,] j is a terminal digraph then the edge V Z is a glue edge, i.e., it is a stable edge that makes the connection of G q ,] j into G.e S (or more precisely the connection of G q ,] j to G q,] j digraph 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 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 at Step 1.
A vertex in G.e S labeled by a bracket ] q j , [ j , ] j ∈ N (3) , that has no adjacent vertex, i.e., the out degree of the vertex labeled by ] q j is 0, is called pop vertex. When connecting a digraph G q ,] j to G.e S , through a pop vertex, if G q ,] j is a terminal digraph, then the final vertex of G q ,] j becomes a final vertex of G.e S . If G q ,] j is not a terminal digraph, then the final vertex of G q ,] j becomes a pop vertex for G.e S .
If there exist more then one vertex labeled by an upper indexed 10 bracket ]q j , [ j , ] j ∈ N (3) , then, if G q ,] j has been already added to G.e S there is no need to add another "copy" of G q ,] j . It is enough to connect ]q j to the digraph existing in G.e S , i.e., to add a new edge ]q j Y , where Y is a sibling of ] j in G q ,] j . This observation holds for any element in G ] j . The procedure described at Step 2 is repeated for each new dummy or pop vertex added to G.e S . For each transformation performed on G.e S , we maintain the same notation G.e S "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).
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 , ] j ∈ N (3) , is a pop vertex, and the digraph G q ,] j that must be added to G.e S has been already connected through a dummy vertex labeled by ]q j (i.e., G q ,] j has been already inserted in G.e S ). According to the procedure described at Step 2 the vertex ] q j is linked to the sibling of ] j in G q ,] j already existing in G.e S . Since the connection of G q ,] j to G.e S has been done through a dummy vertex, the final vertex in G q ,] j cannot be neither a final vertex in G.e S (if G q ,] 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Ḡ ] j the labeled version of G ] j . Then connections through pop vertices will be done by using only digraphs inḠ ] j . However, any dummy vertex ] − j , that is not a pop vertex, obtained by connecting digraphs inḠ ] j to G.e S should be connected to the original digraphs in G ] j , unless a relabeling procedure described at I 1 is required.
r ∪ N (3) }, the set of vertices composing G.e S , in which some brackets may be -marked (by distinctmarkers). To reach the regular language in the Chomsky-Schützenberger theorem we denote by R G the set of all regular expressions obtained by reading G.e S from the initial vertex S to any final vertex. First, suppose that G k does not have an extended grammar. We have K = k and D k = L(G k ). Consider the homomorphism h k : is a regular language with D k ∩ R m = L(G k ). Furthermore, R m is a strength refinement of R, such that the Chomsky-Schützenberger theorem still holds. This is because when building regular expressions in P.e each r.e . The case of λ-loops is taken by the relabeling procedure described at I 1 . 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 2 allows to leave G.e S without re-loading another useless path. That is why the regular language R m built this way is a tighter approximation of L(G k ). A finer language than R m can be 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 2.9) then R G is augmented with ∇ e = {S[ t k+1 , ..., S[ t k+p } and h k is extended  Example 4.2. Consider the context-free grammar in Example 3.7 with the dependency graphs sketched in Figure 3. The set P.e of labeled plus-loop regular expressions built from the dependency graphs is composed of S( Fig. 3 Fig. 3 Fig. 3.e). The extended dependency graph built with respect to the refinement procedure is sketched in Figure 4. The terminal digraphs G 6,] 6 and G 7,] 6 are introduced with respect to the relabeling procedure I 1 , 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 2 ) + to be linked to G 6,] 6 (or to G 7,] 6 ), then when the digraph G 3,] 6 is not added to the corresponding path. Due to the self-loop (] 1 1 ) + , in which ] 1 1 is a pop vertex, we did not applied the relabeling procedure described at I 2 (applying it leads to the same result).

A Regular Superset Approximation for Context-Free Languages
A regular language R may be considered a superset approximation for a context-free language L, if L ⊆ R. A good approximation for L is that 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 (es- pecially in parsing theory) the reader is referred to [21] and [22]. Methods to measure the accuracy of a regular approximation can be found in [4], [8], and [23].
In the sequel we propose a new approximation technique that emerges from the Chomsky-Schützenberger theorem. In brief, the method consists in transforming the original contextfree grammar into a context-free grammar in Dyck normal form. For this grammar we build the refined extended dependency graph G.e S described in Section 4. From G.e S we depict a state diagram A e for a finite automaton and a regular grammar G r = (N r , T, P r , S) that generates a regular (superset) approximation for L(G k ) (which is nothing else than the image through ϕ of the language R m built in Section 4).
Let G k = (N k , T, P k , S) be an arbitrary context-free grammar in Dyck normal form, and G.e S = (V e , E e ) the extended dependency graph of G k . Recall that r ∪ 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 diagram A e can be built by skipping in G.e S all left brackets in N (2) r and all brackets in N (3) , and labeling the edges with the symbol produced by left or right bracket in N (2) ∪ N (1) . This reasoning is applied no matter whether the vertex in V e is -marked or not. Therefore, we avoid -marker specifications when building A e , unless this is strictly necessary. Denote by s f the accepting state of A e . The start state of A e is s S , where S is the axiom of G k . We proceed as follows: 1. There exists an edge in A e from s S to s ] q i , labeled by a, where [ i , ] i ∈ N A L . On the other hand, for an ambiguous grammar G k , there exist several paths (hence regular expressions) in the refined extended dependency graph, which "approximate" the same word in L(G k ). Apparently, finding an unambiguous grammar for L(G k ) may refine the language R m . 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 for L(G k ), it is doubtful that the corresponding regular language R m is finer than the others. In [14] it is also proved that the cost of the "simplicity" is the ambiguity. In other words, finding an unambiguous grammar for L = L(G k ) may lead to the increase in size (e.g. number of nonterminals, rules, levels, etc.) of the respective grammar. Which again, may enlarge R m with 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 paper).
In [4] it is proved that optimal (minimal) superset approximations exist for several kind of context-free languages, but no specification is provided of how the existing minimal approximation can be built starting from the context-free language it approximates. It would be challenging to further investigate whether there exist subsets of context-free languages for which it would be possible to build a minimal superset approximation (by using the graphical method herein proposed).

Conclusions
In this paper we have introduced a normal form for context-free grammars, called Dyck normal form. Based on this normal form and on graphical approaches we gave an alternative proof of the Chomsky-Schützenberger theorem. From a transition-like diagram for a contextfree grammar in Dyck normal form we built a transition diagram for a finite automaton and a regular grammar for a regular superset approximation of the original context-free language. A challenging problem for further investigations may be to further refine this superset approximation depending on the type of the grammar (e.g. nonself-embedding or unambiguous) or on the size of the grammar (e.g. number of nonterminals, rules, etc.) generating a certain context-free language.
The method used throughout this paper is graphically constructive, and it shows that i. derivational structures in context-free grammars can be better described through nested systems of parenthesis (Dyck languages), and ii. the Chomsky-Schützenberger theorem may render a good and efficient approximation for context-free languages. Furthermore, the method provides a graphical framework to handle derivations and descriptional structures in context-free grammars, which may be useful in further complexity investigations of contextfree languages.