Definitions and Notations

A matrix grammar is a regulated rewriting grammar in which rules are grouped into sequences of rules, each sequence defining amatrix. A matrix can be applied if all its rules can be applied one by one according to the order they occur in the matrix sequence. In the case of matrix grammars with appearance checking a rule in a matrix can be passed over if its left-hand side does not occur in the sentential form and the rule belongs to a special set of rules defined within the matrix grammar. Matrix grammars with context-free rules have been first defined in [1] in order to increase the generative power of context-free grammars. The definition has been extended for the case of phrase-structure

Chapter 6. Regulated Rewriting Grammars and Lindenmayer Systems

rules in [60]. The generative power, descriptional and decidability properties, along with several applications of these devices can be found in [14, 54, 56, 60, 62, 79, 146, 188].

Formally, a matrix grammar is defined as follows [54].

Definition 6.1. A matrix grammar is a quintuple G= (N, T, S, M, F) where S is the axiom,N and T,N∩T =∅, are finite sets of nonterminals andterminals, respectively, M = {m₁, m₂, ..., m_k} is a finite set of finite sequences of rules of the form m_j = (pmj,1, pmj,2, ..., pmj,k_mj), where each pmj,i is a phrase-structure rule over N ∪T, 1 ≤ i ≤ k_mj, 1 ≤ j ≤ k, and F is a subset of the rules occurring in the elements of M, i.e., F ⊆ {p_mj,r|1 ≤j ≤k,1 ≤r ≤ kmj}. If F 6= ∅ then G is a matrix grammar with appearance checking and without appearance checking otherwise.

If all rules inM are phrase-structure (PS), context-sensitive (CS), context-free (CF), or regular (REG) rules thenG is a PS, CS, CF, or REG matrix grammar, respectively.

Definition 6.2. Let G = (N, T, S, M, F) be a matrix grammar and V =N ∪T. We say that x∈V⁺ directly derivesy ∈V^∗ inappearance checking mode by application of a rule p of the form α → β, α ∈ (N ∪T)^∗N(N ∪T)^∗ and β ∈ (N ∪T)^∗, denoted by x⇒^ac_p y, if one of the following conditions holds i. x=x1αx2 and y=x1βx2, orii.the rule α→β is not applicable to x, i.e.,α is not a substring of x,p∈F, and x=y.

Note that, if rulepin Definition6.2satisfies conditioni., then we say thatpis effectively applied. If G is a matrix grammars without appearance checking (F = ∅) then only condition i., in Definition 6.2, has to be checked, and then instead of x ⇒^ac_p y the notationx⇒_py is used.

Definition 6.3. Let G = (N, T, S, M, F) be a matrix grammar and V = N ∪T. For m_j = (p_mj,1, p_mj,2, ..., p_mj,kmj),k_mj ≥1, 1≤j≤k, andx, y∈V^∗, we define a derivation step in G, denoted as x ⇒_mj y, by x = x0 ⇒^ac_p

mj ,1 x1 ⇒^ac_p

mj ,2 x2 ⇒^ac_p

mj ,3 ... ⇒^ac_p

mj ,kmj

x_kmj =y (and by x=x₀ ⇒_{pmj ,1} x₁ ⇒_{pmj ,2} x₂ ⇒_{pmj ,3} ...⇒_p

mj ,kmj x_kmj =y if F =∅).

The language L(G) generated by Gis defined as the set of all words w∈T^∗ such that there is a derivation D:S ⇒_mj

1 y1 ⇒_mj

2 y2 ⇒_mj

3 ...⇒_mjq w, 1≤ji ≤k, 1≤i≤q.

Denote byL(M, X) (L(M, X, ac)) the class of languages generated by matrix grammars with appearance checking (without appearance checking, respectively) with X-rules¹, X∈ {REG, CF −λ, CF, CS, P S}.

Let G = (N, T, S, M, F) be a matrix grammar with M = {m₁, m₂..., m_k}. According to Definition 6.2 when a matrix mj, 1≤j≤k, becomes active in appearance checking mode, rules inm_j belonging to F can be passed over if they cannot be applied, i.e., the

1That is all rules inmj∈M, 1≤j≤k, are of type X. Recall that byCF−λwe denote the class of non-erasing context-free rules, i.e., rules of the formα→β, whereα∈N,β∈(N∪T)⁺.

nonterminal rewritten by a rule inmj, and belonging toF, does not occur in the senten-tial form. However, rules inm_j must be effectively applied, if this is possible. If F =∅ then all rules in mj must be effectively applied in the order they occur inmj. When a matrixm_j is applied we say that a derivation step inGis consumed. When a rule inm_j is applied (according to Definition6.2) we say that a derivation step inm_j is consumed.

Since rules in a matrix grammar are arranged into matrices, and rules inside each matrix are applied in a predefined order, it is more convenient to associate labels with matrices than with rules. In this manner each terminal derivation in a matrix grammar can be expressed as a word over the set of labels associated in one-to-one correspondence with the matrices in the grammar, such that labels are concatenated in the same order they have been used during the derivation. Informally, the Szilard language associated with a matrix grammar is the set of all words obtained in this way. In the sequel, for the sake of simplicity, we use the same notation both for a matrix and the label associated with it. Formally, we have [38,39]

Definition 6.4. Let G= (N, T, S, M, F) be a matrix grammar, M ={m₁, m2, ..., m_k} the set of matrices ofG,L(G) the language generated byG, andw∈L(G). TheSzilard word of w associated with the derivation D: S ⇒_mj

1 y1 ⇒_mj

2 y2 ⇒_mj

3 ... ⇒_mjq w in G is defined as Sz_D(w) =m_j1m_j2...m_jq, m_ji ∈M, 1≤j_i ≤k, 1 ≤i≤q. The Szilard language of Gis Sz(G) ={Sz_D(w)|w∈L(G), D is a derivation ofw}.

At each step of derivation a context-free matrix grammar nondeterministically chooses which matrix is applied. Once a matrix becomes active, it works deterministically, in the sense that the order in which the rules are applied is predefined by their order in the matrix sequence. However, the order in which multiple occurrences of a nonterminal in a sentential form are rewritten, is still nondeterministically chosen. A possibility to reduce the nondeterminism in context-free matrix grammars is to impose an order in which nonterminals occurring in a sentential form can be rewritten. As in the case of Chomsky grammars, the most significant are the leftmost-like derivation orders, such as leftmost of type i, i ∈ {1,2,3}, defined and studied in [56, 60, 79, 146, 188]. For context-free matrix grammars, they are formally defined in [60], as follows:

Definition 6.5. Let G= (N, T, S, M, F) be a context-free matrix grammar, with or without appearance checking. A derivation in Gis called

• leftmost-1 if each rule used in the derivation rewrites the leftmost nonterminal occurring in the current sentential form,

• leftmost-2 if at each step of derivation the leftmost occurrence of a nonterminal which can be rewritten (by first rules of matrices that can be effectively applied, with no restrictions on the other rules) is rewritten,

Chapter 6. Regulated Rewriting Grammars and Lindenmayer Systems

• leftmost-3 if each rule used in the derivation rewrites the leftmost occurrence of its left-hand side in the current sentential form.

In other words, forleftmost-1 derivation in matrix grammars without appearance check-ing, each rule in the sequence that defines a matrix rewrites the leftmost nonterminal occurring in the current sentential form (otherwise the matrix cannot be applied in the leftmost-1 derivation manner). In matrix grammars with appearance checking, if a cer-tain rule of a matrix cannot rewrite the leftmost nonterminal, because the nonterminal rewritten by the rule does not occur in the sentential form, then the rule is passed over if it belongs toF. If the nonterminal rewritten by the rule occurs in the sentential form, but this is not the leftmost nonterminal in the sentential form, then the rule, and hence the matrix, cannot be applied in the leftmost-1 manner on that branch of derivation.

A matrix is applied in leftmost-2 derivation manner if the first rule in the matrix se-quence rewrites the leftmost nonterminal that can be rewritten by any matrix. Hence, a matrix m_j can be applied in leftmost-2 derivation manner, if the first rule of m_j (ef-fectively applied, for the case of appearance checking) rewrites the first occurrence of a nonterminalX, and no other matrixm_j⁰ exists such that the first rule inm_j⁰ (effectively applicable) rewrites a nonterminalX⁰, whereX⁰ occurs beforeX in the sentential form on which mj is applied. No other restrictions are imposed on the other rules of mj. A matrix is applied in leftmost-3 derivation manner if each rule of the matrix rewrites the leftmost occurrence of its left-hand side in the sentential form. If a certain rule in the matrix cannot rewrite the leftmost occurrence of its left-hand side (because this does not occur in the sentential form) then the rule is passed over if it belongs toF.

Szilard languages associated with leftmost-i derivations are defined in the same way as in Definition6.4with the specification thatDis a leftmost-iderivation ofw. Denote by SZM^ac(CF) (SZM(CF)) andSZM L^ac_i (CF) (SZM L_i(CF)) the classes of Szilard lan-guages and leftmost-i, i∈{1,2,3}, Szilard languages of matrix grammars with appear-ance checking (matrix grammars without appearappear-ance checking) with context-free rules.