Evolution and observation – a non-standard way to generate formal languages. (English) Zbl 1070.68065

Summary: In 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 previously introduced P/O systems 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.


68Q45 Formal languages and automata
Full Text: DOI


[1] M. Cavaliere, P. Leupold, Evolution and observation—a new way to look at membrane systems, in: A. Alhazov, C. Martı́n-Vide, Gh. Păun (Eds.), Tech. Rep. No. 28/03 Research Group on Mathematical Linguistics, Tarragona; Pre-proc. of the Workshop on Membrane Computing 2003, Tarragona, Spain; http://pizarro.fll.urv.es/continguts/linguistica/proyecto/reports/wmc03.html. · Zbl 1202.68185
[2] S. Crespi-Reghizzi, D. Mandrioli, Petri nets and commutative grammars, Tech. Rep. 74-5, Istituto di Elettrotecnica ed Elettronica—Politecnico di Milano, 1974. · Zbl 0354.68098
[3] Dassow, J; Păun, Gh, Regulated rewriting in formal language theory, (1989), Springer Berlin
[4] Hopcroft, J.E; Ullmann, J.D, Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA
[5] M. Kudlek, C. Martı́n Vide, Gh. Păun, Towards a formal macroset theory, in: C. Calude, Gh. Paun, G. Rozenberg, A. Salomaa (Eds.), Multiset Processing, Lecture Notes in Computer Science, vol. 2235, Springer, Berlin, 2001, pp. 123-133.
[6] G. Rozenberg, A. Salomaa, Watson-Crick complementarity, universal computations and genetic engineering, Tech. Rep. 96-28, Department of Computer Science, Leiden University, 1996.
[7] G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Springer, Berlin, 1997. · Zbl 0866.68057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.