Evolution and observation—a non-standard way to generate formal languages

AbstractIn biology and chemistry a standard proceeding is to conduct an experiment, observe its progress, and then take the result of this observation as the final output. Inspired by this, we have introduced P/O systems (A. Alhazov, C. Martı́n-Vide, Gh. Păun, Pre-Proc. of the Workshop on Membrane Computing 2003, Tarrragona, Spain; http://pizarro.fll.urv.es/continguts/linguistica/proyecto/reports/wmc03.html), where languages are generated by multiset automata that observe the evolution of membrane systems.Now we apply this approach also to more classical devices of formal language theory. Namely, we use finite automata observing the derivations of grammars or of Lindenmayer systems. We define several modes of operation for grammar/observer systems. In two of these modes a context-free grammar (or even a locally commutative context-free grammar) with a finite automaton as observer suffices to generate any recursively enumerable language. In a third case, we obtain a class of languages between the context-free and context-sensitive ones