1$, i.e., from the shuffle of sequences from $\bigcup_{i=1}^t m_i^*$ where $$M=\{m_1,\ldots,m_t\}.$$ The language families generated by vector and semi-matrix grammars are denoted by ${{\bf V}}^{[{\lambda}]}$ and ${{\bf sMAT}}^{[{\lambda}]}$.

A *Petri net* (PN) is a construct $N = (P, T, F, \phi)$ where $P$ and $T$ are disjoint finite sets of *places* and *transitions*, respectively, $F \subseteq (P\times T) \cup (T\times P)$ is the set of *directed arcs*, $$\varphi: (P\times T) \cup (T\times P) \rightarrow \{0, 1, 2, \dots\}$$ is a *weight function*, where $\varphi(x,y)=0$ for all $(x,y)\in ((P\times T) \cup (T\times P))-F$. A mapping $$\mu: P \rightarrow \{0,1,2, \ldots\}$$ is called a *marking*. For each place $p\in P$, $\mu(p)$ gives the number of *tokens* in $p$. $^{\bullet}x=\{y{:}\, (y,x)\in F\}$ and $x^{\bullet}=\{y{:}\, (x,y)\in F\}$ are called the sets of *input* and *output* elements of $x\in P\cup T$, respectively.

A sequence of places and transitions $\rho=x_1x_2\cdots x_n$ is called a *path* if and only if no place or transition except $x_1$ and $x_n$ appears more than once, and $x_{i+1}\in x^\bullet_{i}$ for all $1\leq i\leq n-1$. We denote by $P_\rho, T_\rho, F_\rho$ the sets of places, transitions and arcs of $\rho$. Two paths $\rho_1$, $\rho_2$ are called *disjoint* if $P_{\rho_1}\cap P_{\rho_2}=\emptyset$ and $T_{\rho_1}\cap T_{\rho_2}=\emptyset$. A path $\rho=t_{1}p_{1}t_{2}p_{2}\cdots p_{k-1}t_{k}$ ($\rho=p_{1}t_{1}p_{1}t_{2}\cdots t_{k}p_{1}$) is called a *chain* (*cycle*).

A transition $t \in T$ is *enabled* by marking $\mu$ iff $\mu(p)\geq \phi(p,t)$ for all $p\in P$. In this case $t$ can *occur*. Its occurrence transforms the marking $\mu$ into the marking $\mu'$ defined for each place $p \in P$ by $\mu'(p)=\mu(p)-\phi(p,t)+\phi(t,p)$. This transformation is denoted by $\mu\xrightarrow{t}\mu'$. A finite sequence $t_1t_2\cdots t_k$ of transitions is called *an occurrence sequence* enabled at a marking $\mu$ if there are markings $\mu_1, \mu_2, \ldots, \mu_k$ such that $\mu \xrightarrow{