A programmable DNA automaton model for context-free grammers

Da Ruan, W.-G. Li, Y.-S Ding, Z.-D. Huang, S.-H. Shao, Nadia Messaoudi

    Research outputpeer-review


    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
    StatePublished - Jul 2005
    EventICIS 2005 - The 8th Joint Conference on Information Sciences - Salt Lake City, Utah
    Duration: 21 Jul 200526 Jul 2005


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

    Cite this