A programmable DNA automaton model for context-free grammers

Research output: Contribution to report/book/conference proceedingsIn-proceedings paper


  • Da Ruan
  • W.-G. Li
  • Y.-S Ding
  • Z.-D. Huang
  • S.-H. Shao

Institutes & Expert groups

Documents & links


Context-free grammars (CFGs) are widely applied in character string modeling. The languages accepted by CFGs are also accepted by pushdown automaton (PDA), and vice verse. Taking palindrome language as an example, we propose a novel method to construct a programmable DNA-based PDA, which is equivalent with the CFGs. We give out the nucleotides encoding for input alphabets, stack alphabets, the detectors to report the final result of PDA, and the transition rules. The major features of our method are demonstrated as follows: (1) to encode the components of PDA, we use general linear double-strands DNA (dsDNA) but not circular dsDNA; (2) we only use one restriction enzyme (FokI), that is employed for not only the transiting to state but also the operating to stack.


Original languageEnglish
Title of host publicationProceedings of JCIS 2005
Place of PublicationSalt Lake City, Utah, United States
Publication statusPublished - Jul 2005
EventICIS 2005 - The 8th Joint Conference on Information Sciences - Salt Lake City, Utah, United States
Duration: 21 Jul 200526 Jul 2005


ConferenceICIS 2005 - The 8th Joint Conference on Information Sciences
CountryUnited States
CitySalt Lake City, Utah


  • DNA computing model, programmable, context-free grammars

ID: 365266