【摘要】 本文给出了语言同构和自动机同构的概念。讨论了语言同构的一些性质,语言同构和自动机同构之间的关系。证明了至少有两个元素的字母表上,r.e.语言,上下文有关语言,上下文无关语言以及正规语言按同构组成的等价类之集,都是可数集合。更多还原

【Abstract】 In this paper,the isomorphism of languages and the isomorphism of automatas are discussed.Some properties of the isomorphism of languages are given .The relation between the isomorphism of languages and the isomorphism of automatas is studied. If an alphabet ∑, has at least two members,then the following properties are proved.1)the set of r.e. languages that are not CSL’S is countably infinite. 2)The set of context-sinsitive languages that are non—CFL’S is countably infinete. 3) The set of context-free languages that are not regular sets is countably infinite. 4) The set of regular sets is countably infinite.更多还原