Morphic Characterizations of Language Families Based on Local and Star Languages

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(T _k ∩ F_R) for some 2-star language F_R, an extended 2-star language T _k and a weak coding h.

(ii) Each λ-free context-free language L can be expressed as L = h(D _n ∩ F_L) for some 2-local language F_L and a projection h.

(iii) A language L is accepted by a chemical reaction automaton iff there exist a 2-local language F_L and a weak coding h such that L = h(B _n ∩ F_L),

where D _n and B _n 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.