Evolution and Observation: A Non-standard Way to Accept Formal Languages
Evolution and Observation: A Non-standard Way to Accept Formal Languages
复制标题
进化与观察：接受形式语言的非标准方式
DOI：
10.1007/978-3-540-31834-7_12
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Peter Leupold
中科院分区：
文献类型：
--
作者：
M. Cavaliere;Peter Leupold
在生物学中，观察一个实验的过程，并把这个观察的结果看作是最终的结果，这是一个非常常见的程序。受此启发，引入了一种新的生成形式语言的方法，称为进化/观察[6]。在目前的工作中，我们认为进化/观察作为一种新的策略，也接受语言：一个词被接受，如果（观察到的）从这个输入开始的某个系统的进化遵循一个规则的模式。我们得到以下结果：检查（观察到的）的上下文无关系统的进化是否遵循一个规则的模式是足以接受每一个递归可重复的语言。另一方面，如果我们使用非常简单的规则（类似于→B）来观察系统的演化，那么就有可能完全接受上下文敏感语言的类别。
It is a very common procedure in biology to observe the progress of an experiment and regard the result of this observation as the final outcome. Inspired by this, a new approach for generating formal languages, called evolution/observation, has been introduced [6]. In the current work we consider evolution/observation as a new strategy also for accepting languages: a word is accepted, if the (observed) evolution of a certain system starting from this input follows a regular pattern.We obtain the following result: checking if the (observed) evolution of a context-free system follows a regular pattern is enough to accept every recursively enumerable languages. On the other hand, if we observe the evolution of systems using very simple rules (of the kinda→b), then it is possible to accept exactly the class of context-sensitive languages.