ω-正则语言族的几个子类
-
摘要: ω-语言是有穷字母表(sum from)上的无穷串所构成的集合,被工作在无穷串上的所谓的ω-有穷自动机接受的ω-语言称为ω-正则语言.1中给出的关于ω-正则语言的一些条件,是由ω-有穷自动机与ω-右线性文法描述的.本文通过在(sum from)上的一切ω-字组成的集合(sum from)ω上引进的二元关系"≤ω",定义了ω-左凸语言和ω-右凸语言.从而利用ω-语言的ω-左凸性质、ω-右凸性质,从集合的角度给出了ω-语言是ω-正则语言的几个充分条件.主要结果是:若一个(sum from)上的ω-语言L是闭的且L/(sum from)ω是(sum from)上的正则集,则L是(sum from)上的ω-正则语言;若一个(sum from)上的ω-语言是闭的ω-左凸语言,则它是ω-正则语言;若一个(sum from)上的ω-语言是闭的ω-右凸语言,则它是ω-正则语言.
下载: