在一类ω-语言中ω-正则的特征

CHARACTER OF ω REGULAR IN A CLASS OF LANGUAGES

本文定义了由∑上的ω-语言所确定的∑~∞上的ω-Nerode等价关系的概念以及∑上的ω-语言为左逆封闭的ω-语言的概念。在此基础上证明了:(1)∑上的ω-正则语言必可表示为∑~∞上的某个具有有穷指数的、左不变的等价关系的某些等价类之并。(2)∑上的ω-正则语言所确定的ω-Nerode等价关系的指数必有穷。(3)设L是∑上的左逆封闭的ω-语言,若L所确定的ω-Nerode等价关系的指数有穷,则L必为ω-正则语言。从而,本文从代数、集合的角度给出了在∑上左逆封闭的一类ω-语言中,ω-正则语言的特征。

This paper defined the concept of the ω-Nerode equivalence relation over Σ~ω which is determined by the ω-language over Σ and the concept of left-inverse-closed ω-language. On the base,we proved; (l)an ω-regular language can be represented by the union of some equivalence classed of some equivalence relation with finite index,left-invariant over Σ~ω. (2) The index of the ω-Nerode equivalence relation defined by an ω-regular language over Σ is finite. (3)suppose L is the left-inverse-closed ω-language over S,if the index of the ω-Nerode equivalence relation defined by the L is finite,then the L is ω-regular language. Thus in a class ω-language with left-inverse-closed, the character of the ω-regular language is given from algebra and set viewpoint in this paper.