{'fraction_non_alphanumeric': 0.04863516696688375, 'fraction_numerical': 0.007724816405708743, 'mean_word_length': 3.7040899462277985, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Weak Greibach Normal Form for Hyperedge Replacement Grammars

It is known that hyperedge replacement grammars are similar to string context-free grammars in the sense of definitions and properties. Therefore, we expect that there is a generalization of the well-known Greibach normal form from string grammars to hypergraph grammars. Such generalized normal forms are presented in several papers; however, they do not cover a large class of hypergraph languages (e.g. languages consisting of star graphs). In this paper, we introduce a weak Greibach normal form, whose definition corresponds to the lexicalized normal form for string grammars, and prove that every context-free hypergraph language (with nonsubstantial exceptions) can be generated by a grammar in this normal form. The proof presented in this paper generalizes a corresponding one for string grammars with a few more technicalities.


Introduction
Extensions of formal grammars and languages from strings to graphs are considered in a wide variety of works. The resulting formalisms called graph grammars generate graph languages by means of productions: each production is of the form A → G; it allows one to replace a part of a graph labeled by A with the graph G if certain conditions are satisfied. An overview on graph grammars can be found in "Handbook on Graph Grammars and Computing by Graph Transformation" [11].
In this paper, we focus on a particular approach called hyperedge replacement grammar (HRG). An overview on HRG can be found in the book [7] or in a chapter of the handbook mentioned above [3]. In brief, a hyperedge replacement grammar contains productions that allow one to replace an edge with a certain label by a hypergraph; the rest is similar to string context-free grammar definitions. HRGs appeared in the seventies, and they became popular from theoretical and practical points of view; particularly, they can be used in machine translation or programming (see, for instance, [9]). Many structural properties of HRGs have been studied. Nicely, many theorems regarding context-free string grammars (CFGs) can be extended to HRGs in a natural way; besides, it is often the case that proofs for CFGs can be generalized to HRGs so there is no need to invent anything new.
For context-free grammars, there is a so-called Greibach normal form, which is helpful in a number of investigations, e.g. to connect CFGs with categorial grammars (see [2]). Each production in a grammar in the Greibach normal form has to begin with a terminal symbol and proceed with at most two nonterminal ones. This definition can be weakened: one says that a grammar is in the weak Greibach normal form (it is often called lexicalized) if there is exactly one terminal symbol in the right-hand side of each production. Obviously, the same definition can be introduced for graphs. Namely, an HRG is said to be in the weak Greibach normal form if for each production A → H the hypergraph H has exactly one edge labeled by a terminal symbol.
The main objective of this paper is to present a precise class of graph languages that can be generated by HRGs in the weak Greibach normal form. In order to do this we generalize the proof of existence of the Greibach normal form for context-free grammars taken from [1] in a straightforward way. However, several differences exist. Firstly, there is a nonsubstantial class of hypergraph context-free languages that cannot be generated by grammars in the weak Greibach normal form (a problem arises because of isolated nodes). Secondly, there is a trick in the proof for CFGs that exploits the string nature of grammars, so it is hard to generalize it to hypergraphs. This led us to a large and technically heavy proof. Finally, there are bad news regarding algorithmical complexity: conversion of an HRG into an equivalent one in the weak Greibach normal form cannot be done even in exponential time.
In Sect. 2 we compare our contribution with other studies related to the Greibach normal form for graph grammars. In Sect. 3 formal definitions related to hypergraphs and HRGs are presented. In Sect. 4 the weak Greibach normal form is introduced, related issues are discussed. Sect. 5 is devoted to the main theorem. In Sect. 6 we discuss algorithmic complexity of the normalization procedure. In Sect. 7 we conclude.

Related Work
There are several works devoted to the Greibach normal form for graph grammars. The paper of Joost Engelfriet [4] establishes that HRGs that produce languages of bounded degree are equivalent to apex HRGs; this result generalizes the double Greibach normal form for CFGs. To recall, a language L is of bounded degree if for some M all nodes of all hypergraphs in L have degree not exceeding M. Obviously, there are substantive examples of languages of unbounded degree: for instance, the language of star graphs, which have one node and arbitrarily many edges outgoing from it. Besides, the property of being apex is stronger than the weak Greibach normal form we are interested in.
In the paper of Christina Jansen et al. [8] the local Greibach normal form is presented. The authors prove that data structure grammars (it is a specific kind of grammars that generate so-called heap configurations) can be transformed into grammars in the local Greibach normal form; after the proof the authors point out that the normalization can be generalized to HRGs of bounded degree. However, the authors also note that their procedure being algorithmically efficient cannot be generalized to all HRGs.
The weak Greibach normal form in the sense we are interested in is introduced for another type of graph grammars. Namely, in [5] it is proved that each B-eNCE grammar (here we do not consider definitions regarding this formalism) is equivalent to a B-eNCE grammar in the weak Greibach normal form. In [6] it is shown that B-edNCE grammars and HRGs have the same recognizing power in some sense (namely, since B-edNCE grammars produce usual graphs with labeled nodes and edges while HRGs produce hypergraphs with labeled edges, the result is established w.r.t. two translations, from graphs to hypergraphs and vice versa). However, it seems to be impossible that these two results can be combined in order to obtain the normal form for HRGs. Therefore, to our best knowledge, the question of whether each HRG is equivalent to an HRG in the weak Greibach normal form has hitherto remained open. We answer it in this paper.

Preliminaries
This section is concerned with definitions related to hypergraphs. All of them are taken from [3]. Note that we use a slightly different notation from that in the handbook mentioned above.

Hypergraphs, Sub-hypergraphs
N includes 0. The set of integers from 1 to n is denoted by [1, n].
It is convenient for us to use the following notation: if {i 1 , . . . , i k } is an indexed set of integers such that for m < n i m < i n holds, then it is called index-ordered and the set is denoted as {i 1 , . . . , i k } IO . The set Σ * is the set of all strings over the alphabet Σ including the empty string ε. The length |w| of the word w is the number of positions in w. The i-th symbol in w is denote by w(i) (1 ≤ i ≤ |w|). Σ + denotes the set of all nonempty strings. The set Σ is the set of all strings consisting of distinct symbols. The set of all symbols contained in the word w is denoted by [w]. If f : Σ → ∆ is a function from one set to another, then it is naturally extended as a function f : Let C be some fixed set of labels, for which the function type : C → N is considered.

Definition 1.
A hypergraph over C is a tuple G = V, E, att, lab, ext where V is the set of nodes, E is the set of hyperedges, att : E → V assigns an ordered set of attachment nodes to each edge, lab : E → C labels each hyperedge by some element of C in such a way that type(lab(e)) = |att(e)| whenever e ∈ E, and ext ∈ V is an ordered set of external nodes. Components of a hypergraph G are denoted by V G , E G , att G , lab G , ext G .
In the remainder of the paper, hypergraphs are simply called graphs, and hyperedges are simply called edges. The set of all graphs with labels from C is denoted by H (C). In this work, figures contain graph drawings and sketches. In drawings, nodes are depicted by black dots, edges are denotes as labeled boxes, att is represented with numbered lines (called "tentacles"), external nodes are depicted by numbers in brackets. If an edge has type 2, it is depicted by an arrow. If we are not interested in a specific form of a graph but we want to have a closer look at some its part, we depict the whole graph as an area but draw its part of interest in detail. Example 1. This is a graph: If G is a graph, and e ∈ E G is labeled by a, then G can be denoted by G(e : a).
Definition 2. The function type (or type G to be exact) returns the number of nodes attached to some edge in a graph G: type G (e) := |att G (e)|. If G is a graph, then type(G) := |ext G |.  Definition 5. An isomorphism between graphs G and H is a pair of bijective functions E : In this work, we do not distinguish between isomorphic graphs.

Replacement
This procedure is defined in [3]. In short, the replacement of an edge e 0 in G with a graph H can be done if type(e 0 ) = type(H) as follows: 1. Remove e 0 ; 2. Insert an isomorphic copy of H (namely, H and G have to consist of disjoint sets of nodes and edges); 3. For each i, fuse the i-th external node of H with the i-th attachement node of e 0 .
To be more precise, the set of edges in the resulting graph is (E G \ {e 0 }) ∪ E H , and the set of nodes is

Hyperedge Replacement Grammars
Definition 6. A hyperedge replacement grammar (HRG) is a tuple HGr = N, Σ, P, S , where N is a finite alphabet of nonterminal symbols, Σ is a finite alphabet of terminal symbols (N ∩ Σ = / 0), P is a set of productions, and S ∈ N. Each production is of the form A → H where A ∈ N, H ∈ H (N ∪ Σ) and type(A) = type(H). For π = A → H we denote lhs(π) = A, rhs(π) = H.
Edges labeled by terminal (nonterminal) symbols are called terminal edges (nonterminal edges resp.). If a graph contains terminal edges only, it is called terminal.
G is said to derive H. The corresponding sequence of production applications is called a derivation.
Definition 7. The language generated by an HRG HGr = N, Σ, P, S is the set of graphs H ∈ H (Σ) such that (S) * ⇒ H. It is denoted by L(HGr). A graph language L is said to be a hypergraph context-free language (HCFL) if it is generated by some HRG.
Two grammars are said to be equivalent if they generate the same language.
Further we simply write A * ⇒ G instead of (A) * ⇒ G.

Weak Greibach Normal Form
In this section we introduce the formal definition of the normal form we are interested in, and establish a simple property of languages generated by grammars in this normal form.
Definition 8. An HRG HGr is in the weak Greibach normal form (WGNF) if there is exactly one terminal edge in the right-hand side of each production. Formally, ∀(X → H) ∈ P HGr ∃!e 0 ∈ E H : lab H (e 0 ) ∈ Σ HGr .
Example 2. The grammar HGr 1 = {S}, {a}, P 1 , S is in the WGNF where P 1 contains the following rules (type(S) = type(a) = 1): This grammar generates the language of star 1-edged a-labeled hypergraphs, which is unbounded. Remark 1. If N, Σ, P, S is in the WGNF and X k ⇒ G for some X ∈ N, then G has exactly k terminal edges (each production adds exactly one terminal edge).
Note that not each hypergraph context-free language can be generated by some HRG in the WGNF. This follows from Example 3. Consider the HRG HGr 2 = {T }, {b}, P 2 , T where P 2 contains the following rules (type(T ) = type(b) = 0): The first production just adds an isolated node; thus this grammar produces graphs that have exactly one edge labeled by b and arbitrarily many isolated nodes. If there is an equivalent HGr = N, {b}, P , S in the WGNF, then each right-hand side of each production in P contains exactly one terminal edge. Note that if S k ⇒ G, G ∈ H ({b}) for some k in HGr , then G has k terminal edges (Remark 1); hence k has to be equal to 1 and therefore S → G ∈ P . However, there are infinitely many graphs in L(HGr) while |P | < ∞.
It is seen that the reason of this problem is in isolated nodes. In the string case if a language contains the empty word, then it cannot be generated by a grammar in the WGNF due to obvious reasons: each production adds at least one terminal symbol so it is impossible to produce the empty word. In the case of graphs, we also have to prohibit somehow undesired languages with "too many" isolated nodes occuring in graphs.
Below we describe the precise class of languages generated by grammars in the weak Greibach normal form. We denote by esize(G) the number of edges in G, and by isize(G) the number of isolated nodes in G.
Definition 9. An HCFL L is said to be isolated-node bounded (ibHCFL) if there is a constant M such that, for each G ∈ L, isize(G) < M * esize(G). An HRG HGr is called isolated-node bounded if it generates an ibHCFL.
The other direction of this statement is of central interest in this paper. The next section is devoted to it.

Transformation of HRGs Generating IBHCFLs into HRGs in the Weak Greibach Normal Form
The main theorem we are going to prove is the following: Each ibHCFL L can be generated by an HRG in the WGNF.
In other words, this theorem states that each context-free hypergraph language satisfying the isolatednode boundedness property can be generated by a grammar in the weak Greibach normal form.
Structurally, the proof of this theorem is based on the corresponding one for string context-free grammars. Let us recall the mains steps of the latter in brief (see details in [1]).
The input of the algorithm is a context-free grammar CFG that does not generate the empty word (this property is related to isolated-node boundedness). The desired output is an equivalent grammar in the weak Greibach normal form (i.e. in which each production is of the form A → aA 1 . . . A n where a is terminal while A 1 , . . . , A n are nonterminal).
1. Useless rules and symbols, ε-rules (i.e. rules of the form A → ε) and chain rules (i.e. rules of the form A → B for A, B being nonterminal) are eliminated.
2. It is shown how to eliminate recursive A-productions, i.e. productions of the form A → Aα for some fixed nonterminal symbol A. The trick is to move A from the left side of Aα to the right side. It is done as follows: if A → Aα 1 | . . . |Aα m |β 1 | . . . |β p are all the A-productions (here | means enumeration of productions), then they are replaced by the productions 3. Left recursion is completely eliminated: nonterminals are numbered as A 1 , . . . , A n and then a procedure involving application of step 2 is done such that its result is a grammar where each production is either of the form A i → A j α for i < j or of the form A i → bα for b being terminal.
4. By taking compositions of the above productions and adding new nonterminal symbols the grammar is normalized. The resulting grammar includes rules of the form A → bα (b is terminal, α is a string of nonterminals) only.
Our goal is to recreate this proof for HRGs. Note that steps 2-4 of the above plan actively exploit string nature of CFGs: transformations of productions are based on movements of symbols from the leftmost position to the rightmost one. Graphs in general do not have leftmost positions unlike strings, so we are going to distinguish arbitrary edges in graphs so they play the role of "the leftmost symbol". It is done by means of δ (see the proof below).
In the proof we use the following It directly follows from the well-known context-freeness lemma.

Eliminating Useless, Edgeless and Chain Productions
Our first objective is to eliminate useless productions, productions with no edges in the right-hand side and productions with one nonterminal edge only in the right-hand side. It appears that only this step requires isolated-node boundedness. In the below transformations we provide theoretical reasonings that they can be done irregarding their algorithmic realization; however, the latter can be done similarly to the string case (see [1]).  It suffices to remove all the useless symbols and all the productions containing them. This does not affect the language generated.
Definition 11. A graph is called edgeless if it does not contain edges. A production A → G is called edgeless if G is edgeless.

Method.
Let  Thus we removed all the productions having a graph with one edge in the right-hand side. It can be easily shown that L(HGr ) = L(HGr). Remark 2. If HGr in Transformation 3 does not have edgeless productions, then HGr does not have them either. Transformations 2 and 3 applied to a grammar without useless symbols transform them into a grammar without useless symbols too. Example 5. The grammar HGr 2 from Example 3 cannot be turned into an equivalent one without edgeless and chain productions.
The above procedures complete the first step of normalization.

Defining and Eliminating Recursive Productions
Now we start proving Theorem 2. Let HGr = N, Σ, P, S be a grammar that generates L. Applying Transformations 1, 2, 3, we can assume that HGr does not have useless symbols, edgeless productions and chain productions. Thus, the right-hand side of each production has at least two edges or one terminal edge. Let us carefully examine what happens in the string case at Step 2. Consider the following Example 6. Let A → Ac|Ad|Be be all the A-productions in a string context-free grammar. After Step 2 there are the following ones: A → BeA |Be, A → c|d|cA |dA . Below we show how a derivation in the old grammar is remodeled in the new one: Old: A ⇒ Ac ⇒ Adc ⇒ Addc ⇒ Beddc. New: A ⇒ BeA ⇒ BedA ⇒ BeddA ⇒ Beddc. The underlying idea is to invert the derivation: in the new derivation one starts with Be and applies new productions in reverse order w.r.t. to the old derivation.
The same idea is used in the graph case. The difficulty is that we do not have the leftmost symbol in productions. However, it suffices to distinguish an arbitrary edge in the right-hand side of each production to play the role of the leftmost symbol. We do this by means of the function δ .
Definition 13. Let us fix an arbitrary function δ which acts on P in such a way that δ (A → H) belongs to E H . We denote µ(π) = lab(δ (π)). Now µ(π) plays the role of the "leftmost" symbol of a production π. Then we define recursive productions as expected.
Definition 15. A derivation A ⇒ H 1 ⇒ · · · ⇒ H k is called a δ -derivation if each of its productions is applied to the edge that is δ of the previous production. Formally, if A ⇒ H k , then π i has to be appied to δ (π i−1 ) (in the subgraph that appears after the (i − 1)-th step). We say that the final label of such a derivation is µ(π k ). Note that µ(π i ) has to be nonterminal for i < k (but µ(π k ) can be terminal).
Below we study how to eliminate all the recursive A-productions for some fixed A ∈ N. In the string case the idea is quite simple: one moves A from the beginning of the string to its end in order to invert a derivation process. Here we also exploit the idea of inverting the derivation but, of course, we have to take into account more complex and general graph structures. Let H k be a δ -derivation such that lhs(π i ) = A for i = 1, . . . , k and µ(π k ) = A (compare this with the old derivation in Example 6). We provide the following intuition behind the below construction. Imagine that one has a hole in his sweater (this metaphor is related to that in [4]), and he sews it up starting from edges (i.e. he applies π 1 , . . . , π k−1 ) and finishing by sewing on a patch in the center of the hole (i.e. he applies π k ). In the new derivation one starts with the patch (that is, the right-hand side of π k ), then he sews up right-hand sides of π k−1 , . . . , π 2 in this order (thus the patch grows and becomes bigger) and finishing by connecting it with edges of the hole w.r.t. the production π 1 (see also Fig. 5 which provides a sketch of this process). The major problem of this idea is the following: if we want to invert a derivation such as on Figure  5a and to obtain a new one, such as one drawn on Figure 5b, we have to carefully control external nodes. Namely, in the old derivation external nodes of H are predefined by R 1 while in the new derivation R 1 appears at the very last step. In order to place external nodes correctly, we introduce complex nonterminal symbols that describe how external nodes of a graph on the current derivation step correspond to external nodes of a graph on the next and on the last step. This description is done by means of partial functions. Now we proceed with formal realization of this idea. Let t = type(A). Let ρ 1 = A → R 1 , . . . , ρ K = A → R K be all the recursive A-productions in P and let γ 1 = A → G 1 , . . . , γ L = A → G L be the remaining Aproductions in P. Our goal is to construct a grammar equivalent to HGr without recursive A-productions. Firstly, we simply remove them: P 1 := P \ {ρ 1 , . . . , ρ K }. In order to compensate for the lack of these rules we add new ones accordingly to the procedure below. A → R A (1) . . . (t) . . .  Definition 16. f : X → Y is a partial function if f is a function on some subset X of X. We denote the domain X of f by Dom( f ), and the range of f by Ran( f ).
Definition 17. f : X → Y is a partial bijection if f is a partial function such that f | Dom( f ) is a bijection.
Definition 18. If f : X → Y , g : Y → Z are partial functions, then g • f : X → Z is a partial function defined on Dom( f ) ∩ f −1 (Dom(g)) that acts on this set as a usual composition.
(2) . . .  Type II. Production of type II are used at the last step of a derivation such a on Fig. 5b; returning to the metaphor they allow one to finish sewing up and to finally connect a patch (that has grown by applying productions of types I and III) with the edges of a hole. We recall that ρ = A → R such that δ (ρ) = e 0 ∈ E R and lab(e 0 ) = A. Let f 0 : [1,t] → [1,t] be a function which is defined by the following relation: f 0 (i) = j ⇔ att R (e 0 )(i) = ext R ( j). Obviously, f 0 is a partial bijection. We set • Let k be equal to |Dom( f 0 )| and let [1,t] \ Ran( f 0 ) = { j 1 , . . . , j t−k } IO . Then ext = att R (e 0 )ext R ( j 1 ) . . . ext R ( j t−k ).
Thus the production is defined correctly. Type III. Productions of type III serve to make a "sewing up step" from inside to outside. f , g that specify relations between external nodes on the current step, on the next step and on the final step are changed by related functions f , g . Let f , g, f , g : [1,t] → [1,t] be partial bijections. The whole procedure described below can be done if g • f = g.
We say that P 2 is obtained from P 1 by adding all possible productions of all the above types. Obviously, their number is finite (each production is defined by at most four partial functions from [1,t] to [1,t]). Lemma 2. The grammar HGr 1 = N , Σ, P 2 , S is equivalent to HGr = N, Σ, P, S .
Proof. Informally, it suffices to notice that the design of new productions allows one to invert productions in the way which is shown on Figure 5. Example 7 provides an illustration of the formal proof, which is given below.
Firstly, we check that L(HGr) ⊆ L(HGr 1 ). In order to do that, we show how to model a branch of a derivation that consists of rules of the form ρ i and finishes with a rule γ j by means of HGr 1 . Let A ⇒ . . . Figure 4: The production ν 3,ρ, f ,g, f ,g . Here R denotes a graph R without δ (ρ).
Let G k be defined inductively as follows: To prove the claimed inclusion, it suffices to show then that A ⇒ . . , m. Then G i+1 can be considered as a subgraph of G i := R i [G i+1 /δ (ρ i )], which is a subgraph of H. Let f i be a partial function defined by the following correspondence: f i ( j) = k ⇔ ext G i+1 ( j) = ext G i (k). Similarly we define g i : g i ( j) = k ⇔ ext G i ( j) = ext H (k). It follows from these definitions that g i • f i = g i−1 .
Let σ i = A → G i+1 and G i := rhs(ν 1,σ i , f i ,g i ). We prove by the reverse induction on p = m, . . . , 1 that then A ⇒ Basis. Since σ m = A → G = γ is not a recursive A-production, we added ν 1,σ m , f m ,g m in our grammar. This completes the basis case.
Step. We assume by the induction hypothesis that A ⇒ HGr 1 G p and our aim is to prove the same for p − 1. G p contains an edge labeled by (A, f p , g p ). Then a type III rule is applied to this edge: ν 3,ρ p , f p ,g p , f p−1 ,g p−1 . The design of such rules allows us to perform exactly the substitution of G p+1 into R p . Therefore, A ⇒ HGr 1 G 1 . Note that the right-hand side of this derivation contains an edge labeled by (A, f 1 , g 1 ). Since G 1 = H, we see that g 1 is the identity function id. Thus we can apply the type II rule of the form ν 2,ρ 1 whose left-hand side equals (A, f 1 , id) = (A, f 1 , g 1 ). This rule is also designed in such a way that its application is equivalent to substitution of G 2 into R 1 . This means that A ⇒ . . .
. . .  Now, if there is an arbitrary derivation where the rule ρ i is applied (1 ≤ i ≤ K), then we find the largest δ -derivation within the derivation that includes this occurence ρ i and remodel it as described above. Thus, the above reasonings complete the proof for one of the inclusions.
To prove the reverse inclusion, it suffices to show how to transform a branch of a derivation containing nonterminals of the form (A, f , g) into a derivation in HGr. Let Note that functions f i and g i in the first derivation can be arbitrary (they only have to satisfy the condition of type III rules); however, it is not hard to show that they are the same as the functions f i and g i that are built on the basis of the second derivation. This finishes the proof.
There are two important observations regarding the procedure and the lemma above: 1. After such a procedure there are no recursive A-productions; 2. For each nonterminal (A, f , g) there is no rule π such that µ(π) = (A, f , g).
Note that HGr 1 does not preserve all the properties that HGr had. Namely, rules of Type II can contain only one edge. However, our further actions do not affect type II and type III rules so this does not matter. Besides, useless symbols can appear, which also does not bother us (we deleted them only to perform Transformations 2 and 3). This finishes the second step.
Example 7. Let a grammar contain two A-productions: the first one is recursive and the second one is not recursive. They are depicted below; δ of each production is represented by the red color.  (1)

4
⇒ G Here f 3 (1) = 2, f 3 (2) = 3; f 1 = f 2 = f 3 = g 2 ; g 3 (1) = 3; g 1 = id are all the involved partial functions; it is easy to check that they actually satisfy conditions from definitions. Note that if n is the total number of derivation steps, then f i specifies a relation between external nodes on the (n−i)-th and on the (n−i+1)th steps and it is defined by a corresponding production in the old derivation. In this example, f i are all defined by the production ρ, thus they are the same. g i defines a relation between external nodes on the (n − i + 1)-th step and external nodes at the end of a derivation (on the n-th step). As expected, g 1 is the identity function since n = 4 and (n − 1 + 1) = n, so g 1 specifies a relation between external nodes on the last and on the last step.

Eliminating Recursion and Convertion into the WGNF
The rest of the steps are similar to those in the string case. Let us start with HGr; let N = {A 1 , . . . , A m }. Then the following transformation is done.
However, if we consider only HRGs of order r for some fixed r (i.e. in which types of symbols are not greater than r), then the above example ceases to be a problem as well as the first and the second steps in our proof since the number of partial bijections from [1; r] to itself (and, in particular, the size of S r ) is constant when r is fixed.

Conclusion
Our desire to introduce the weak Greibach normal form appeared due to another research about hypergraph basic categorial grammars (we presented a paper [10] about them at ICGT-2020); in that work we introduce a new approach to describing graph languages and prove that each grammar in this new formalism can be transformed into an equivalent HRG in the WGNF and vice versa. Theorems 1 and 2 show that ibHCFL is exactly the class of languages generated by grammars in the weak Greibach normal form; thus we also answer a question about the recognizing power of hypergraph basic categorial grammars -they also generate exactly ibHCFL. Besides, we suppose that the issue of the WGNF is a fundamental theoretical question, and we have presented an answer in line with those in [4,8]. Note that the result gives a natural grammar characterization of the language class ibHCFL.