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

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