Research On The Theory And Application Of Bimolecular Pushdown Automaton

DNA computing aims at using nucleic acids for computing. Since Adleman's successful solution of a seven-vertex instance of the NP-complete Hamiltonian directed path problem by a DNA algorithm initiated the field of biomolecular computing in 1994. In the past ten years, both the theory and the experiment method of DNA computing were improved greatly.DNA solutions can act as billions of parallel nanoprocessors with few consume. The biomoluclar automata base on DNA computing is a kind of nano-computer. It's difference to the original DNA computing that This DNA computing model can realized the base function of automaton.An automata made of biomolecules can combine the strongpoint of the DNA computing and electrical computing. It can also improve the practicability of DNA computer and extend the application of DNA computing.In this paper, the restriction enzymes were analyzed for detail it infection to construct a finite automata made of biomolecules. Base on this result, a finite automaton with more state and symbol had been constructed.Here a new finite automata made of biomolecules was described, which can be used as a programmable pushdown store. A new kind of restriction enzyme was used in this model. Which have two recognition sites and cut side between two recognitions? The basic mechanism of a simple pushdown store and an improved pushdownstore was studied. The programmable ability and the efficiency of this kind of pushdown store are influenced by the coding of the Symbol biomolucule and the restriction enzyme. Base on this result, a special enzyme and a suitable coding must be choosen to maximize the programmable ability and the efficiency of the biomolucula pushdown store. This pushdown store is also a programmable automaton. A tag molecule should be used to extend the pushdown store to a completely programmable automaton. This programmable automaton gains the advantage over the basic one. Such as simplify the coding, increase the step of computing and keep the transition information.Bimolecular pushdown automatons can construct with a finite automaton and a pushdown store. Obviously, the pushdown automaton is more powerful than the finite automaton.The application of bimolecular automaton is discussed in this paper too. The power of bimolecular automaton is less than electronic computer now. But the bimolecular automaton can used in some special area for it's a nano-meter computer. Such as diagnosis and treat the disease, detect atom material and use in encrypt the information etc. It's also can used too store some information, construct some bimolecular pool etc.