摘要
DNA分子计算的工作原理是对生物系统进行编码,以生物化学反应为基础,利用生物技术实现生物系统的状态转移来推进计算过程.2001年以色列的Yaakov Benenson等人在基于DNA计算的发卡模型实现了具有状态转移功能的分子有限状态自动机,国内则有利用DNA计算的方法构造可编程分子下推存储器的相关研究.该存储器基于分子自动机的原理,能按一定逻辑进行自组装,是一种纳米尺度的生物存储机构.文中首先通过在分子有限自动机上扩展一个分子下推存储器从而获得了一种简单的分子下推自动机,并基于该下推自动机提出了一类语言的分子自动机解法.接着提出了两种改进的分子下推自动机的模型,通过增加模型复杂度,分别解决了基本型分子下推自动机存在输入字符串限制和输入分子形式不统一的问题.计算理论表明,该种下推自动机的计算能力超过了已有的有限自动机.
DNA computing aims at using nucleic acids for computing. DNA solutions can act as billions of parallel nanoprocessors with few consume. A biomolecular finite automaton has been realized by Benenson in 2001, and the programmable biomolecular pushdown store based the DNA computing is available too. This pushdown store can self assemble with certain logical. In this paper, a simple biomolecular pushdown automaton is constructed with a finite automaton and a pushdown store firstly, and an algorithm is designed to solve a kind of languages. In addition, two improved pushdown automata are designed to solve some problems exiting in the original pushdown store. One of them can accept input string with infinite symbols in theory, and the other can uniform the input symbol. The pushdown automata described in this paper are more powerful than the existing finite automaton in computing theory.
出处
《计算机学报》
EI
CSCD
北大核心
2008年第12期2168-2172,共5页
Chinese Journal of Computers
基金
国家自然科学基金(60674106,60703047)
图像处理与智能控制重点实验室开放基金(200703)资助
关键词
分子下推自动机
DNA计算
biomolecular pushdown automaton
DNA computing
