计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (28): 83-85.DOI: 10.3778/j.issn.1002-8331.2008.28.029

• 研发、设计、测试 • 上一篇    下一篇

DNA编码文法的分析与设计

马芳芳1,宋 弢1,李 涵2   

  1. 1.山东科技大学 信息科学与工程学院,山东 青岛 266510
    2.山东科技大学 信息系,山东 泰安 271019
  • 收稿日期:2008-05-13 修回日期:2008-07-30 出版日期:2008-10-01 发布日期:2008-10-01
  • 通讯作者: 马芳芳

Analysis and research on DNA encoding grammar

MA Fang-fang1,SONG Tao1,LI Han2   

  1. 1.College of Information Science and Engineering,Shandong University of Science and Technology,Qingdao,Shandong 266510,China
    2.College of Information,Shandong University of Science and Technology,Tai’an,Shandong 271019,China
  • Received:2008-05-13 Revised:2008-07-30 Online:2008-10-01 Published:2008-10-01
  • Contact: MA Fang-fang

摘要: DNA编码问题是DNA计算中初始数据库的设计问题,DNA编码优劣直接影响DNA计算的成功与否。提出了将DNA编码视为是某个文法产生的语言的思想,并且证明了DNA编码文法的存在性;进而通过化简文法的字母表,将DNA编码文法的设计问题转化为二进制文法的设计问题;同时设计出产生某个具体DNA编码的文法,最后得到了DNA编码文法的两个性质。

关键词: DNA计算, DNA编码, Hamming距离, 形式语言, 图灵机

Abstract: DNA encoding is a problem of designing initial solutions in DNA computing,and the quality of the DNA codes can determine whether the DNA computing is successful or not.In this paper,we propose the method which takes a DNA code as a language formed by some grammar and prove the existence of the DNA encoding grammar.Then,by simplifying the alphabet of the grammar,we make the design of DNA encoding be equal to that of the binary grammar.Synchronously,we contrive a grammar which can produce a concrete DNA encoding.Finally,we get two properties of the DNA encoding grammar.

Key words: DNA computation, DNA encoding, Hamming distance, formal language, Turing machine