Let L be any class of languages, L' be one of the classes of context-free, context-sensitive and recursively enumerable languages, and Σ be any alphabet. In this paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h:Γ*Σ* defined by h(a)=a for aΣ and h(a)=λ (empty word) for aΓ-Σ, a Dyck language D over Γ, and a language L1 in L' over Γ such that L=h(DL1). (2) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses Xk, Dyck reduction Red over Xk, and a language L2 in L' over ΣXk such that L=Red(L2)Σ*. We also give an application of this result.

Let L be any class of languages, L' be a class of languages which is closed under λ-free homomorphisms, and Σ be any alphabet. In this paper, we show that if the following statement (1) holds, then the statement (2) holds. (1) For any language L in L over Σ, there exist an alphabet of k pairs of matching parentheses Xk, Dyck reduction Red over Xk, and a language L1 in L' over ΣXk such that L=Red(L1)Σ*. (2) For any language L in L over Σ, there exist an alphabet Γ including Σ, a homomorphism h : Γ*Σ*, a Dyck language D over Γ, and a language L2 in L' over Γ such that L=h(DL2). We also give an application of this result.