A Necessary and Sufficient Condition for Controlled Generation of Right Linear Grammars with Unknown Behaviors

This paper deals with a formal language theoretic framework for the generation of DNA nanostructures by DNA hybridization control. In order to model such processes of generating DNA linear nanostructures, Kimoto et al. proposed right linear grammars with unknown behaviors (RLUBs, for short), in which behavior of derivation is not determined completely, and only the upper bound and the lower bound of behaviors of derivations are known beforehand. In bio-lab experiments, it is required to control the generation process (chemical reaction process) in order to output only a target nanostructure even if we do not know completely the behavior of chemical reaction process. Kimoto et al. focused on the problem of controlling the generation process of RLUBs using control systems in order to output a target string using as few control devices (control symbols) as possible. However, there has been no general discussion about which language classes can be generated by the control of RLUBs. This paper deals with the general theory on finite classes of finite languages to be generated by the control of RLUBs. In particular, we consider physical properties of control devices used in control systems in a detailed manner and formulate them as quasiorders over control alphabets of control systems. We give a necessary and sufficient condition for given finite classes of finite languages to be generated by RLUBs and their control systems with the constraint of a given quasiorder over the control alphabet. The obtained results would be the first step toward the construction of the theory for answering to the question from bio-lab experiment researchers of whether the physical properties of devices affect the ability to generate nanostructures.