Affiliations: [a] Faculty of Arts and Science, Kyushu University, 744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan. fokubo@artsci.kyushu-u.ac.jp | [b] Faculty of Education and Integrated Arts and Science, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050 Japan. yokomori@waseda.jp
Correspondence:
[‡]
Address for correspondece: Department of Mathematics, Faculty of Education and Integrated Arts and Science, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050 Japan
Note: [*] Partly supported by Grants-in-Aid for JSPS Fellows No.16K16008, Japan Society for the Promotion of Science.
Note: [†] Partly supported by JSPS KAKENHI, Grant-in-Aid for Scientific Research (C) 17K00021 of The Ministry of Education, Culture, Sports, Science, and Technology, Japan, and by Waseda University grant for Special Research Project: 2017K-121.
Abstract: New morphic characterizations in the form of a noted Chomsky-Schützenberger theorem are established for the classes of regular languages, of context-free languages and of languages accepted by chemical reaction automata. Our results include the following: (i) Each λ-free regular language R can be expressed as R = h(Tk ∩ FR) for some 2-star language FR, an extended 2-star language Tk and a weak coding h. (ii) Each λ-free context-free language L can be expressed as L = h(Dn ∩ FL) for some 2-local language FL and a projection h. (iii) A language L is accepted by a chemical reaction automaton iff there exist a 2-local language FL and a weak coding h such that L = h(Bn ∩ FL), where Dn and Bn are a Dyck set and a partially balanced language defined over the n-letter alphabet, respectively. These characterizations improve or shed new light on the previous results.
Keywords: Regular languages, Context-free languages, Chemical reaction automata, Morphic characterizations, Star languages, Local languages
