Formal language prerequisites

We present the basic notions and notations used in the dissertation, for further information the reader is referred to [SalomaaSalomaa1973],  [Rozenberg and SalomaaRozenberg and Salomaa1980] and [Dassow and PaunDassow and Paun1989].

The set of all non-empty words over a finite alphabet $V$ is denoted by $V^+$, the empty word is denoted by $\lambda$; $V^*=V^+\cup \{\lambda\}$. For a set $V$, we denote by card$(V)$ or by $\vert V\vert$ the cardinality of $V$. For a word $x$, we denote by $\vert x\vert$ the length of $x$. If $a\in V$ and $x$ is a word over $V$, then ${\vert x\vert}_a$ denotes the number of letters $a$ in $x$. When $V_1\subseteq V$ and $x\in V^*$, then ${\vert x\vert}_{V_1}={\sum}_{a\in V_1}{\vert x\vert}_a$.

If $V$ is an alphabet, then $V^{(2)}$, $V'$, $[V,i,j]$, and $[V,j]$ denote the sets $\{x^{(2)}\;\vert\;x\in V\}$, $\{x'\;\vert\;x\in V\}$, $\{[x,i,j]\;\vert\;x\in V\}$, and $\{[x,j]\;\vert\;x\in V\}$ for $1\leq i,j$, respectively.

If $x=x_1\cdots x_n$ is a word over an alphabet $V$, where $x_j\in V$ for $1\leq j\leq n$, then $[x,i,k]$ and $[x,i]$ denote the words $[x_1,i,k]\cdots[x_n,i,k]\in {[V,i,k]}^*$ and $[x_1,i]\cdots[x_n,i]\in {[V,i]}^*$, respectively, for $i,k\geq 1$; $x'$ and $x^{(2)}$ denote the words ${x_1}'\cdots {x_n}'\in {V'}^*$ and $x_1^{(2)}\cdots x_n^{(2)}\in {V^{(2)}}^*$.

Let $V$ be an alphabet and $x,y\in V^*$. We use the notation $x\preceq y$ if $x$ is a sub-word of $y$, that is, if $y=x_1xx_2$ with some words $x_1,x_2\in V^*$.

By a permutation of the words $w_1,\ldots,w_n$, written as ${[w_1,w_2,\ldots,w_n]}^P$, where $w_i\in V^*$ for $1\leq i \leq n$, we mean a word in the form of $w_{i_1}w_{i_2}\cdots w_{i_n}$, where $i_{j_1}\not = i_{j_2}$ if $j_1\not =j_2$ and $1\leq i_j\leq n$ for $1\leq j\leq n$.

By a language over an alphabet $V$ we mean a subset $L$ of $V^*$. We denote by alph$(L)$ the set of all letters appearing in at least one word of $L$. For a word $w$, alph$(w)$ denotes the set of all letters appearing in $w$.

By a context-free production or by a context-free rule (a CF rule, for short) over an alphabet $V$ we mean a production in the form of $a\ensuremath{\rightarrow}u$, where $a\in V$ and $u\in V^*$. A CF rule is a $\lambda$-rule (or a deletion rule) if $u=\lambda$.

For a set of CF rules $R$, dom$(R)$ denotes the set of all letters appearing on the left-hand side of a rule in $R$.