A programmable DNA automaton model for context-free grammers

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.