next up previous contents
Next: Team behaviour of simple Up: Preliminaries Previous: Lindenmayer systems   Contents

Simple eco-grammar systems

We give only the definition of simple eco-grammar systems. The formal definition of the original (i.e. non-simple) version, which was introduced in [Csuhaj-Varjú, Kelemen, Kelemenová, and PaunCsuhaj-Varjú et al.1997] is not presented, because in this dissertation we study only simple eco-grammar systems. For more details about the original version see [Csuhaj-Varjú, Kelemen, Kelemenová, and PaunCsuhaj-Varjú et al.1997].

Definition 2.1  
A simple eco-grammar system (a simple EG system, for short) is a construct \ensuremath{\Sigma=(\:V_E,P_E,R_1,\ldots,R_n,
\omega\:)}, where

In this construct $ V_E$ is the alphabet and $ P_E$ is the set of evolution rules of the environment. The $ i$th agent is represented by the set $ R_i$, $ 1\leq i \leq n$. String $ \omega$ is the axiom, the initial sentential form.

The system changes its state by a simultaneous action of the agents and by a parallel rewriting done according to $ P_E$: in each derivation step first each agent rewrites one letter in the sentential form, then the environment rewrites the remaining letters in a parallel way.

Definition 2.2  
Consider a simple eco-grammar system \ensuremath{\Sigma=(\:V_E,P_E,R_1,\ldots,R_n,
\omega\:)}. We say that $ x$ directly derives $ y$ in $ \Sigma$ $ ($with $ x,y\in {V_E}^*$, written as $ x \ensuremath{{\stackrel{\text{eco}\;\;}
{\Longrightarrow}}_{\Sigma}} y)$, if

Let us note here that according to this definition, all the agents have to work in each derivation step. In [ter Beekter Beek1999] and in Chapter 5 another version of simple eco-grammar systems is studied, the so called weak simple eco-grammar system. In this case the derivation is not blocked if some of the agents cannot perform any action on the sentential form.

We denote the transitive and reflexive closure of $ \ensuremath{{\stackrel{\text{eco}\;\;}
{\Longrightarrow}}_{\Sigma}}$ by $ \ensuremath{{\stackrel{\text{eco}\;\;}
{\Longrightarrow}}_{\Sigma}^{*}}$. The generated language consists of all the words which can be derived from the initial string.












Definition 2.3  
Consider a simple eco-grammar system \ensuremath{\Sigma=(\:V_E,P_E,R_1,\ldots,R_n,
\omega\:)}. The generated language of $ \Sigma$ is the following:

$\displaystyle L(\Sigma)=\{ v\in {V_E}^*
\vert\;{\omega} \ensuremath{{\stackrel{\text{eco}\;\;}
{\Longrightarrow}}_{\Sigma}^{*}} v \}.$

The extended version of simple eco-grammar systems, where a subset of the alphabet, called the terminal alphabet is distinguished, was introduced in [Csuhaj-Varjú, Kelemen, Kelemenová, and PaunCsuhaj-Varjú et al.1997].

Definition 2.4  
An extended simple eco-grammar system is a construct $ \Sigma=(\:V_E,P_E,R_1,\ldots,$ \ensuremath{R_n,
\omega,\Delta\:)}, where

In an extended simple eco-grammar system, the derivation goes in the same way as presented in Definition 2.2, the only difference is that the generated language contains only words over the terminal alphabet.

Definition 2.5  
Consider an extended simple eco-grammar system
\ensuremath{\Sigma=(\:V_E,P_E,R_1,\ldots, R_n,
\omega,\Delta\:)}. The generated language of $ \Sigma$ is the following:

$\displaystyle L(\Sigma)=\{ v\in {\Delta}^*
\vert\;{\omega} \ensuremath{{\stackrel{\text{eco}\;\;}
{\Longrightarrow}}_{\Sigma}^{*}} v \}.$


Now we present two examples which illustrates our model and its power.

Example 2.6  
Let $ \Sigma=(\;V_E,P_E,R_1,R_2,R_3,\omega,\Delta\;)$ be the following extended simple EG system:

It is easy to see that the generated language is a non-context-free language: $ L(\Sigma)=\{\; a^nb^nc^n\;\vert\;n\geq 1\;\}$.

Example 2.7  
Let $ \Sigma=(\;V_E,P_E,R_1,R_2,R_3,\omega,\Delta\;)$ be the following extended simple EG system:

When deriving a terminal word, in a derivation step we have only three possibilities: we can use the first rules of the agents together or we can use the second ones or the third ones, otherwise the derivation is blocked because in the next step one of the agents could not work. Therefore either all the agents introduces the same letter $ a$ or $ b$ or the agents finish the derivation by bringing in a $ c$. This implies that the generated language is $ L(\Sigma)=\{\; {(cw)}^3\;\vert\;w\in{\{a,b\}}^*\;\}$, which is a non-$ E0L$ language (see [Ehrenfeucht and RozenbergEhrenfeucht and Rozenberg1976]).


next up previous contents
Next: Team behaviour of simple Up: Preliminaries Previous: Lindenmayer systems   Contents
Csima Judit 2002-01-04