帰納的に可算な言語の補集合演算を用いた特徴付けについて

概要

論文の詳細を見る
There have been many homomorphic characterizations of language classes by a homomorphic image of intersection of two languages. In this note we attempt to find new homomorphic characterizations without intersection and we find that it is possible to characterize the class of recursiveley enumerable languages if complementation is available, that is, we have following characterizations. 1) For every recursively enumerable language L, there exist a context-free language L' and a homomorphism h such that L=h(L')^^^-. 2) For every recursively enumerable language L, there exist a deterministic context-free language L' and two homomorphisms h_1,h_2 such that L=h_1(h_2(L'))^^^-.
八戸工業大学の論文
1991-03-31